平衡二叉树

发表于 | 分类于 |
字数统计: 1.1k 字 | 阅读时长 ≈ 5 分钟

题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]

方法一：BFS 广度优先搜索

利用队列先进先出的特性

  • 首先根元素入队
  • 当队列不为空的时候
    • 求当前队列的长度 n
    • 依次从队列中取 n 个元素进行拓展，然后进入下一次迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    if (root == null) {
      return ret;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      List<Integer> level = new ArrayList<>();
      int currentLevelSize = queue.size();
      while(currentLevelSize-- > 0) {
        TreeNode node = queue.poll();
        level.add(node.val);
        if (node.left != null) {
          queue.offer(node.left);
        }
        if (node.right != null) {
          queue.offer(node.right);
        }
      }
      ret.add(level);
    }

    return ret;
  }
}

var levelOrder = function(root) {
  let res = []
  if(root === null) return res
    
  let queue = []
  queue.push(root)
  while(queue.length) {
      let len = queue.length
      let level = []
      while(len--) {
          let node = queue.shift()
          level.push(node.val)
          if(node.left !== null) {
              queue.push(node.left)
          }
          if(node.right !== null) {
              queue.push(node.right)
          }
      }
      res.push(level)
  }
  return res
};

复杂度分析

  • 时间复杂度：O(n)，每个点进队出队各一次，故渐进时间复杂度为 O(n)
  • 空间复杂度：O(n)，队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了94.14%的用户

  • 内存消耗：38.8 MB, 在所有 Java 提交中击败了7.41%的用户

方法二：DFS 递归

用广度优先处理是很直观的，可以想象成是一把刀横着切割了每一层，但是深度优先遍历就不那么直观了。

4.jpg

我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子。田字形的每一层就对应一个 list。

5.jpg

按照深度优先的处理顺序，会先访问节点 1，再访问节点 2，接着是节点 3。
之后是第二列的 4 和 5，最后是第三列的 6。

每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。

动态演示如下：

0203_1.gif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;	
class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(root == null) return res;

    dfs(1, root, res);
    return res;
  }

  public void dfs(int index, TreeNode root, List<List<Integer>> res) {
    //假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
    if(res.size() < index) {
      res.add(new ArrayList<Integer>());
    }
    //将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
    //res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
    res.get(index - 1).add(root.val);
    //递归的处理左子树，右子树，同时将层数index+1
    if(root.left != null) {
      dfs(index +1, root.left, res);
    }
    if(root.right != null) {
      dfs(index+1, root.right, res);
    }
  }
}

var levelOrder = function(root) {
  let res = []
  if(root === null) return res
  dfs(1, root, res)
  return res
};

var dfs = function(level, root, res) {
  //假设res是[ [1],[2,3] ]， level是3，就再插入一个空数组放到res中
  if(res.length < level) {
    res.push([])
  }
  //将当前节点的值加入到res中，level代表当前层，假设level是3，节点值是99
  //res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
  res[level - 1].push(root.val)
  //递归的处理左子树，右子树，同时将层数+1
  if(root.left !== null) {
    dfs(level + 1, root.left, res)
  }
  if(root.right !== null) {
    dfs(level + 1, root.right, res)
  }
  return
}

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(h)，h 是树的高度

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：38.8 MB, 在所有 Java 提交中击败了15.66%的用户