LeetCode DFS、BFS篇(102)

102. 二叉树的层序遍历

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

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

3

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

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

//思路1BFS，优化广度遍历，一层一层放进deque进行遍历,遍历完一层就用list装完加入res
//思路2DFS，每一层递归都用index做标记

solution1 BFS 迭代

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if (root != null) {
            deque.add(root);
        }
        while (!deque.isEmpty()){
            int n = deque.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0;i<n;i++){
                TreeNode node = deque.pop();
                level.add(node.val);
                if (node.left!=null){
                    deque.add(node.left);
                }
                if (node.right!=null){
                    deque.add(node.right);
                }
            }
            res.add(level);
        }
        return res;
    } 
}

solution 2 DFS 递归

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        dfs(res,root,1);
        return res;
    }
    public void dfs(List<List<Integer>> res,TreeNode node,int index){
        if (res.size()<index){
            res.add(new ArrayList<Integer>());
        }
        res.get(index-1).add(node.val);
        if (node.left != null){
            dfs(res,node.left,index+1);
        }
        if (node.right != null){
            dfs(res,node.right,index+1);
        }
    }
}

LeetCode DFS、BFS篇(102)

原文：https://www.cnblogs.com/gg12138/p/13308148.html