LeetCode刷题小记——层序遍历

没事就刷刷

题目

开始干

解法

• 迭代——利用队列
• 递归

迭代

顺序：从上到下，从左到右。很有秩序，多适合用队列啊！

迭代的写法其实类似于图的BFS（广度优先搜索）

思想：利用队列的先进先出的特点，每次出队一个节点，就把他的孩子往后排，按照左、右的顺序加入队尾（年轻然要讲武德，不许插队）。

思路：

1. 初始化，根节点入队
2. 出队，并把它的孩子加入队尾
3. 重复step 2

代码：

/**
 * 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<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();	//很讲武德的队列
        //判空
        if(root == null)return res;
        //根节点入队
        queue.offer(root);
        //开始迭代
        while(!queue.isEmpty()){
            //一个存放当前层序列的list
            List<Integer> list = new ArrayList<>();
            Integer len = queue.size();//当前层 节点的个数，用来控制出队次数
            for(int i = 0; i<len; i++){
                //出队，加入list
                TreeNode node = queue.poll();
                list.add(node.val);
                //如果有孩子，加入队列，不用担心越层，因为有len控制
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //把当前层的list加入res
            res.add(list);
        }
        return res;
    }
}

递归

看起来迭代的写法也就很好了，但是递归可以解。

迭代的解法借鉴BFS，那么我们是否能够借鉴DFS（深度优先搜索，树的先序遍历）来解呢？

看似DFS不太行，但是只要我们控制好层数，按层放置，也是可行的。（DFS也是从左到右，类似于树的先序遍历）。

**思想：**利用层数分开放置，孩子的层数是父亲的层数+1，再结合先序遍历的总体从左到右遍历，即可完成序列放置。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //初始化  全局变量
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        //判空
        if(root == null)return res;
        fun(root,0);
        return res;
    }
    public void fun(TreeNode root,Integer level){
        if(root == null) return ;
        if(level == res.size())//表示res里没有当前层的list，没有就建立一个
            res.add(new ArrayList<Integer>());
        //拿到当前level的list
        List<Integer> list = res.get(level);
        //类似于树的先序遍历，但是我们用level来归类放置
        list.add(root.val);
        //DFS优先搜索树
        fun(root.left,level+1);
        fun(root.right,level+1);
    }

}

这次看似迭代更好理解一些！