1/16, various traversal in tree

Preorder ***

Inorder *****

Postorder ****

level order *****

vertical order ****

Morris traversal(preorder, inorder) ****

typical questions related: ....

• Binary Tree Right Side View
• Recover Binary Search Tree

1: Preorder

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return res;
    }
}

preorder with parent pointer: is it possible to perform iterative pre-order traversal on a binary 
tree without using node-stacks or "visited" flags?

public static void printPreorder(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        System.out.println(cur.val);

        if (cur.left != null) {
            cur = cur.left;
        } else if (cur.right != null) {
            cur = cur.right;
        } else {
            while (cur.parent != null && (cur.parent.right == null 
                    || cur == cur.parent.right)) {
                cur = cur.parent;
            }
            if (cur.parent == null) break;
            cur = cur.parent.right;
        }
    }
}

2: Inorder

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.pop();
            list.add(node.val);

            cur = node.right;
        }
        return list;
    }
}

3: postorder

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root, prev = null;
        stack.push(root);

        while (!stack.isEmpty()) {
            cur = stack.peek();

            if (prev == null || prev.left == cur || prev.right == cur) {
            // cur is under the prev pointer, need to explore all the node below the cur
                if (cur.left != null) {
                    stack.push(cur.left);
                } else if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else if (cur.left == prev) {
            // explore all the node in the right
                if (cur.right != null) stack.push(cur.right);
            } else {
            // process current node
                res.add(cur.val);
                stack.pop();
            }
            prev = cur;
        }
        return res;
    }
}

note: while loop only need !stack.isEmpty() as condition. In addition, the traversal order is left, right, mid.

4: level order

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Deque<TreeNode> queue = new LinkedList<>();
        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);
            }

            res.add(list);
        }
        return res;
    }
}

recursive level order:   pre-order dfs over binary tree

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

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

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

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

5: vertical order

314: Binary tree vertical order traversal

offset + level order traversal
class Solution {
    private class Tuple{
        int offset;
        TreeNode node;
        public Tuple(int offset, TreeNode node) {
            this.offset = offset;
            this.node = node;
        }
    }
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Map<Integer, List<Integer>> map = new HashMap<>();
        Deque<Tuple> queue = new LinkedList<>();
        queue.offer(new Tuple(0, root));

        int min = 0, max = 0;
        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            map.putIfAbsent(t.offset, new ArrayList<>());
            map.get(t.offset).add(t.node.val);

            min = Math.min(min, t.offset);
            max = Math.max(max, t.offset);
            if (t.node.left != null) queue.offer(new Tuple(t.offset - 1, t.node.left));
            if (t.node.right != null) queue.offer(new Tuple(t.offset + 1, t.node.right));
        }

        for (int i = min; i <= max; i++) {
            res.add(new ArrayList<>(map.get(i)));
        }
        return res;
    }
}

note:

• Attempt to use DFS to solve the problem, but you cannot guarantee all the elements in list are ordered.
• You can choose TreeMap, because key in treemap is ordered, but time complexity of insert is higher, O()

6: Morris

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;

        while (cur != null) {
            if (cur.left == null) {
                res.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode pre = cur.left;
                // explore the right most node in cur.left
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }

                if (pre.right == null) {
                    pre.right = cur;
                    // res.add(cur.val);    preorder traversal
                    cur = cur.left;
                } else {
                    pre.right = null;  // restore structure
                    res.add(cur.val);  // inorder traversal
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}

note: 每次访问root 左子树之前，先找到左子树里面最右面的点，并把其right指针连到root上，左子树遍历完这个点之后，再把这个多出来的指针拆掉。space complexity: O(1)

Binary Tree Right Side View

recursive solution: level starts by 1, and increments by one when exploring the tree deeper.

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

        dfs(res, 1, root);
        return res;
    }

    private void dfs(List<Integer> res, int level, TreeNode root) {
        // base case
        if (root == null) return;
        if (level > res.size()) {
            res.add(root.val);
        }

        // recursive case
        if (root.right != null) dfs(res, level + 1, root.right);
        if (root.left != null) dfs(res, level + 1, root.left);
    }
}

iterative solution:

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

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

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    list.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return list;
    }
}

Recover Binary Search Tree

method using Inorder Traversal

class Solution {
    public void recoverTree(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root, prev = null;
        TreeNode p = null, q = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();

            if (prev != null && node.val <= prev.val) {
                if (p == null) p = prev;
                q = node;
            }
            prev = node;
            cur = node.right;
        }
        swap(p, q);
    }

    private void swap(TreeNode p, TreeNode q) {
        if (p == null || q == null) return;

        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}

note: 需要知道cur, prev, p, q 之间的关系，当node.val <= prev.val，就出现我们要找的值，在赋值给p和q的时候，注意 q = node; 两次都要进行赋值。

method using Morris traversal

class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        TreeNode cur = root, prev = null;
        TreeNode p = null, q = null;
        while (cur != null) {
            if (cur.left == null) {
                if (prev != null && prev.val >= cur.val) {
                    if (p == null) p = prev;
                    q = cur;
                }
                prev = cur;
                cur = cur.right;
            } else {
                TreeNode temp = cur.left;
                while (temp.right != null && temp.right != cur) {
                    temp = temp.right;
                }
                if (temp.right == null) {
                    temp.right = cur;

                    cur = cur.left;
                } else {
                    temp.right = null;
                    if (prev != null && prev.val >= cur.val) {
                        if (p == null) p = prev;
                        q = cur;
                    }

                    prev = cur;
                    cur = cur.right;
                }
            }
        }
        swap(p, q);
    }
    private void swap(TreeNode p, TreeNode q) {
        if (p == null || q == null) return;

        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}

note: prev = cur; only when processing the current node