5/9, Tree, 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);
    }
}

迭代 ans.add(0, tmp)

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(root==null) return ans;
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i=0;i<size;i++){
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if(cur.left!=null) queue.add(cur.left);
                if(cur.right!=null) queue.add(cur.right);
            }
            ans.add(0, tmp);
        }
        return ans;
    }
}

Binary Tree Zigzag Level Order Traversal

挺 trivial 的问题。加一个reverse的变量

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);
    }

    public void helper(TreeLinkNode left, TreeLinkNode right){
        if(left==null&&right==null) return;
        if(left==null || right==null) return;
        left.next = right;

        TreeLinkNode p = left;
        TreeLinkNode q = right;
        while(q.right!=null && q.left!=null){
            p = p.right;
            q = q.left;
            p.next = q;
        }


        helper(left.left, left.right);
        helper(right.left, right.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) {
        if(root==null) return;
        TreeLinkNode prev = root;

        while(prev!=null){
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode cur = dummy;

            while(prev!=null){

                if(prev.left!=null){
                    cur.next = prev.left;
                    cur=cur.next;
                }
                if(prev.right!=null){
                    cur.next = prev.right;
                    cur=cur.next;
                }
                prev = prev.next;
            }
            prev = 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) {
        if(root==null) return;
        TreeLinkNode prev = root;

        while(prev!=null){
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode cur = dummy;

            while(prev!=null){

                if(prev.left!=null){
                    cur.next = prev.left;
                    cur=cur.next;
                }
                if(prev.right!=null){
                    cur.next = prev.right;
                    cur=cur.next;
                }
                prev = prev.next;
            }
            prev = 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>();
        dfs(root, 1, list);
        return list;
    }

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

        if(level>list.size()){
            list.add(root.val);
        }
        dfs(root.right, level+1, list);
        dfs(root.left, level+1, list);
    }
}

Find Largest Value in Each Tree Row

DFS BFS

Find Bottom Left Tree Value

BFS level order traversal, 没什么可说的, 值得一提的是一个炫技的思路, 可以学习, 不建议用. right-left的添加, 最后一次使用的root节点为ans

public int findLeftMostNode(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null)
            queue.add(root.right);
        if (root.left != null)
            queue.add(root.left);
    }
    return root.val;
}

results matching ""

    No results matching ""