【算法面试通关40讲】28 - 面试题：二叉树层次遍历

Leetcode-102. 二叉树的层次遍历

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

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

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

解法：分别使用BFS和DFS进行解题，时间复杂度相同，都是O(N)。注意如果是使用图的搜索，一定要有set进行node的排重

直观上使用BFS，套用公式

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()){
   
            int levelSize = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i=0;i<levelSize;i++){
   
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

Python

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root: return res
        queue = []
        queue.append(root)
        while queue:
            tmp = []
            levelSize = len(queue)
            for _ in range(levelSize):
                node = queue.pop(0)
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res

DFS

Java
将TreeNode所在的层级作为参数传入，不断在res中添加元素

/** * 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<>();
        this.dfs(res,root,0);
        return res;
        
    }
    public void dfs(List<List<Integer>> res, TreeNode root, int level){
   
        if(root==null) return;
        if(res.size() <= level){
   
            res.add(new LinkedList<Integer>());
        }
        res.get(level).add(root.val);
        this.dfs(res,root.left,level+1);
        this.dfs(res,root.right,level+1);
    }
}

Python

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        self.res = []
        self.dfs(root,0)
        return self.res
    
    def dfs(self,root, level):
        if not root: return 
        if len(self.res) <= level:
            self.res.append([])
        self.res[level].append(root.val)
        self.dfs(root.left,level+1)
        self.dfs(root.right,level+1)

注意由于Python和Java的类特性不同

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        self.dfs(res,root,0)
        return res
        
    def dfs(self, res, root, level):
        if not res: return 
        if len(res) <= level:
            res.append([])
        res[level].append(root.val)
        self.dfs(res,root.left,level+1)
        self.dfs(res,root.right,level+1)