JAVA 牛牛

102. 二叉树的层序遍历

  • May 13, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： DFS BFS
  • 思路： DFS BFS
  • 类似题型:

题目 102. 二叉树的层序遍历

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

示例：

二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解题思路

  • 看到二叉树，首选考虑 DFS BFS
  • 如图：左边是BFS，按照层进行搜索；图右边是DFS，先一路走到底，然后再回头搜索

pic1

方法一 BFS

  • BFS 通常和 队列(Queue) 结合使用，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS总共有两个模板：
    1. 如果不需要确定当前遍历到了哪一层，BFS模板如下 
      while queue 不空：
  cur = queue.pop()
  for 节点 in cur的所有相邻节点：
   if 该节点有效且未访问过：
       queue.push(该节点)
    2. 如果要确定当前遍历到了哪一层，BFS模板如下。
      这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。 
      level = 0
while queue 不空：
  size = queue.size()
  while (size --) {
   cur = queue.pop()
   for 节点 in cur的所有相邻节点：
       if 该节点有效且未被访问过：
           queue.push(该节点)
  }
  level ++;

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root,0,res);
        return res;


    }
    private void dfs(TreeNode root,int deepth,List<List<Integer>> res) {
        if (root ==null) return;
        if (deepth==res.size()) res.add(new ArrayList<>());
        res.get(deepth).add(root.val);
        deepth++;
        dfs(root.left,deepth,res);
        dfs(root.right,deepth,res);

    }
}

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# BFS
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            size = len(queue)
            level = []
            for _ in range(size):
                node = queue.popleft()
                if not node:
                    continue
                level.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            if level: # 如果level 不为空
                res.append(level)
        return res

方法二 DFS

  • DFS 做本题的主要问题是： DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 level。递归到新节点要把该节点放入 level 对应列表的末尾。

  • 当遍历到一个新的深度 level，而最终结果 res 中还没有创建 level 对应的列表时，应该在 res 中新建一个列表用来保存该 level 的所有节点。

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> curr = new ArrayList<>();
            int size = queue.size();
            for(int i = 0;i<size;i++) {
                TreeNode node =  queue.poll();
                if(node ==null) {
                    continue;
                }
                curr.add(node.val);

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }


                if(i==size-1) {
                    res.add(curr);
                }
            }
        }

        return res;
    }
}

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# DFS
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:

        def dfs(root,deepth,res):
            if not root:return # 终止条件
            if deepth==len(res):res.append([])
            res[deepth].append(root.val)
            dfs(root.left,deepth +1,res)
            dfs(root.right,deepth +1,res)
        res = []
        dfs(root,0,res)
        return res
Search