Tree, Level Order Traversal

Binary Tree Level Order Traversal

解法一：用queue去做level order，不写了。

解法二：用dfs做, 本质是一个preorder traversal。

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

        dfs(result, root, 0);
        return result;
    }

    private void dfs(List<List<Integer>> result, TreeNode root, int depth) {
        if (root == null) {
            return;
        }

        if (depth >= result.size()) {
            result.add(new ArrayList<Integer>());
        }
        result.get(depth).add(root.val);

        dfs(result, root.left, depth + 1);
        dfs(result, root.right, depth + 1);
    }
}

Binary Tree Level Order Traversal II

就写DFS的解法了, 每次depth >= result.size()时，在result的头上插入一个新的ArrayList, 然后这个ArrayList的index是result.size() - depth - 1。记得reuslt的类型要用LinkedList，因为都是addFirst()的操作。

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

        dfs(result, root, 0);
        return result;
    }

    private void dfs(LinkedList<List<Integer>> result, TreeNode root, int depth) {
        if (root == null) {
            return;
        }

        if (depth >= result.size()) {
            result.addFirst(new ArrayList<Integer>());
        }
        result.get(result.size() - depth - 1).add(root.val);

        dfs(result, root.left, depth + 1);
        dfs(result, root.right, depth + 1);
    }
}

Binary Tree Zigzag Level Order Traversal

根据不同的操作选择不同的list的类型。还是一个preorder traversal。

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

        dfs(result, root, 0);
        return result;
    }

    private void dfs(List<List<Integer>> result, TreeNode root, int depth) {
        if (root == null) {
            return;
        }

        if (depth >= result.size()) {
            if (depth % 2 == 0) {
                result.add(new ArrayList<Integer>());
            } else {
                result.add(new LinkedList<Integer>());
            }
        }
        if (depth % 2 == 0) {
            result.get(depth).add(root.val);
        } else {
            result.get(depth).add(0, root.val);
        }

        dfs(result, root.left, depth + 1);
        dfs(result, root.right, depth + 1);
    }
}

Populating Next Right Pointers in Each Node

这题的题目给出了这颗树是一个perfect binary tree的条件。

解法一：recursive solution

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null || root.left == null) {
            return;
        }

        root.left.next = root.right;
        if (root.next != null) {
            root.right.next = root.next.left;
        }

        connect(root.left);
        connect(root.right);
    }
}

解法二：iterative solution

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode current = root;
        TreeLinkNode next = null;

        while (current != null && current.left != null) {
            next = current.left;
            while (current != null) {
                current.left.next = current.right;
                if (current.next != null) {
                    current.right.next = current.next.left;
                }
                current = current.next;
            }
            current = next;
        }
    }
}

Populating Next Right Pointers in Each Node II

这题里不默认这个树是perfect binary tree了，可以是任意形状的。

iterative solution: level order的遍历

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode current = root;
        TreeLinkNode next = null;
        TreeLinkNode prev = null;

        while (current != null) {
            while (current != null) {
                if (current.left != null) {
                    if (next == null) {
                        next = current.left;
                    }
                    if (prev == null) {
                        prev = current.left;
                    } else {
                        prev.next = current.left;
                        prev = current.left;
                    }
                }
                if (current.right != null) {
                    if (next == null) {
                        next = current.right;
                    }
                    if (prev == null) {
                        prev = current.right;
                    } else {
                        prev.next = current.right;
                        prev = current.right;
                    }
                }
                current = current.next;
            }

            current = next;
            next = null;
            prev = null;
        }
    }
}

Binary Tree Right Side View

解法一: dfs(preorder traversal)

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

    private void dfs(List<Integer> result, TreeNode root, int depth) {
        if (root == null) {
            return;
        }

        if (depth >= result.size()) {
            result.add(root.val);
        }

        dfs(result, root.right, depth + 1);
        dfs(result, root.left, depth + 1);
    }
}

解法二：level order traversal with queue

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    result.add(node.val);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }

        return result;
    }
}