Level Order traversal

Binary Tree Level Order Traversal

送分题，就当热手了。

迭代的写法和 CLRS 的伪代码一模一样。

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root != null) queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            rst.add(list);
        }

        return rst;
    }
}

这题的递归写法挺有意思的。

• 递归写法本质上是对 binary tree 做了一个 pre-order dfs.

• 更靠近 root 的层一定会比下一层先建出来

• 对于同一个 level，左面的节点一定比右面节点先 add.

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        dfs(rst, root, 0);
        return rst;
    }

    private void dfs(List<List<Integer>> rst, TreeNode root, int level){
        if(root == null) return;

        if(level >= rst.size()){
            rst.add(new ArrayList<Integer>());
        }

        rst.get(level).add(root.val);

        dfs(rst, root.left, level + 1);
        dfs(rst, root.right, level + 1);
    }
}

Binary Tree Level Order Traversal II

写法一样，最后 reverse 一下就好了。

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
       List<List<Integer>> rst = new ArrayList<List<Integer>>();
        dfs(rst, root, 0);
        Collections.reverse(rst);
        return rst;
    }

    private void dfs(List<List<Integer>> rst, TreeNode root, int level){
        if(root == null) return;

        if(level >= rst.size()){
            rst.add(new ArrayList<Integer>());
        }

        rst.get(level).add(root.val);

        dfs(rst, root.left, level + 1);
        dfs(rst, root.right, level + 1);
    }
}

Binary Tree Zigzag Level Order Traversal

挺 trivial 的问题。

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        boolean reverse = false;
        if(root != null) queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            if(reverse) Collections.reverse(list);

            rst.add(list);
            reverse = !reverse;
        }

        return rst;
    }
}

Populating Next Right Pointers in Each Node

Level order 的写法非常的 trivial，不过这题规定不许手动建任何额外空间（不许存level或者用迭代写，虽然递归也用空间）

考虑到这题给定 perfect tree，不需要考虑中间有拐弯或者空位的问题，递归解决的思路就是用一个 helper 函数传入当前的两个节点（为上一个节点的 left/right child）

• 连接左右

• 迭代依次连接左节点右侧的 path 与 右节点左侧的 path

• 递归下一层

public class Solution {

    public void connect(TreeLinkNode root) {
        if(root == null) return;
        if(root.left == null && root.right == null) return;

        helper(root.left, root.right);
    }

    private void helper(TreeLinkNode p, TreeLinkNode q){
        if(p == null && q == null) return;
        if(p == null || q == null) return;

        p.next = q;

        TreeLinkNode l = p;
        TreeLinkNode r = q;
        while(q.right != null && q.left != null){
            p = p.right;
            q = q.left;

            p.next = q;
        }

        helper(l.left, l.right);
        helper(r.left, r.right);
    }
}

真正的 O(1) 空间是用固定数量的指针进行迭代循环。

• 这种写法是真正的 level order 添加，利用了上一层完成之后的 next 指针手动做了 level order 遍历。

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;

        TreeLinkNode cur = root;
        TreeLinkNode leftMost = null;
        while(cur.left != null){
            leftMost = cur.left;
            while(cur != null){
                cur.left.next = cur.right;
                if(cur.next == null){
                    cur.right.next = null;
                } else {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            cur = leftMost;
        }
    }
}

• 在参考了下一题 follow up 的写法之后，这类问题的通解：

public class Solution {
    public void connect(TreeLinkNode root) {
        while(root != null){
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode cur = dummy;
            for( ; root != null; root = root.next){
                if(root.left != null){
                    cur.next = root.left;
                    cur = cur.next;
                }
                if(root.right != null){
                    cur.next = root.right;
                    cur = cur.next;
                }
            }
            root = dummy.next;
        }
    }
}

Populating Next Right Pointers in Each Node II

搞了半天一直处于一个追着各种 test case 改 Bug 的阶段，而且要改的细节越来越多。。。写题如果发现自己陷入了这个阶段，还是果断换思路把。

这题的迭代思路和上一题一样，充分利用好上一层已经是连好的next指针来做 level order. 然而有几个很烦的地方需要处理:

• 中间有空缺节点的话，怎么让上层找到“下一个”正确的节点

• 如果某一层最左边有空缺的话，如何在进入下一层的时候找到正确的起点

这个解法的思路非常简洁优美。因为对题本质的理解更进一步了：

• 我们要做的其实是 level order 建一个 LinkedList 出来。

于是这题几个最烦人的细节处理，都可以靠 dummy node 解决。

• 这题也是继 word ladder 之后另一个不同的 for 循环写法，字符和链表都很适合用 for loop 实现遍历。

public class Solution {
    public void connect(TreeLinkNode root) {
        while(root != null){
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode cur = dummy;
            for( ; root != null; root = root.next){
                if(root.left != null){
                    cur.next = root.left;
                    cur = cur.next;
                }
                if(root.right != null){
                    cur.next = root.right;
                    cur = cur.next;
                }
            }
            root = dummy.next;
        }
    }
}

Binary Tree Right Side View

这题本质上还是在做 level order 遍历，因为最终结果上 node 是按层数依次添加的。

于是回想下递归版的 level order traversal，我们做 dfs pre-order

• 【中，左，右】 的顺序可以保证上面一层的节点永远会比下一层的先建立；

• 同时对于每一层，我们一定会先发现最左面的节点，而后才是右面依次发现。

把这个性质根据题意改一下，我们就有了

• 【中，右，左】 首先保证了 level order，因为对于所有子树，中节点要比左右子树先执行；

• 同时因为子树顺序是 【右，左】，同一 level 的节点一定是从右到左被发现的。

因此只要注意判断条件，只把第一次发现的元素添加进去，然后做改变顺序版 preorder traversal 就好了。

• 同理也很容易解 Left Side View.

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();

        helper(root, list, 0);

        return list;
    }

    private void helper(TreeNode root, List<Integer> list, int level){
        if(root == null) return;

        if(level == list.size()) list.add(root.val);
        helper(root.right, list, level + 1);
        helper(root.left, list, level + 1);
    }
}