Traverse

Binary Tree Traversal: Preorder, Postorder, Inorder, Levelorder (Top-down, Bottom-up, Zigzag) Pre-order: root-left-right

Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, return [1,2,3]. 1 \ 2 / 3 Note: Recursive solution is trivial, could you do it iteratively?

Solution

Use a Stack: Time ~ O(N), Space ~ O(N) 先找到最左节点，然后一层层往上返回，没返回一层节点，要进入其右子树遍历（重复该过程）。

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// root-left-right
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null)   return list;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null) {
        list.add(curr.val);
        stack.push(curr);
        curr = curr.left;
    }

    while (!stack.isEmpty()) {
        curr = stack.pop();
        curr = curr.right;
        while (curr != null) {
            list.add(curr.val);
            stack.push(curr);
            curr = curr.left;
        }
    }

    return list;
}

Post-order: left-right-root

Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively?

Solution

Use a Stack: Time ~ O(N), Space ~ O(N) 先用mirrored preorder：root-right-left 然后再reverse整个结果：left-right-root

// left-right-root
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null)   return list;
    Stack<TreeNode> stackBack = new Stack<>();  // mirrored preorder
    Stack<Integer> stack = new Stack<>();       // store mirrored preorder results
    TreeNode curr = root;

    while (curr != null) {
        stack.push(curr.val);
        stackBack.push(curr);
        curr = curr.right;
    }

    while (!stackBack.isEmpty()) {
        curr = stackBack.pop();
        curr = curr.left;
        while (curr != null) {
            stack.push(curr.val);
            stackBack.push(curr);
            curr = curr.right;
        }
    }

    // reverse: root-left-right (preoder) => right-left-root (postorder)
    while (!stack.isEmpty()) {
        list.add(stack.pop());
    }
    return list;
}

In-order : left-root-right

Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively?

Solution

1. Use a Stack: Time ~ O(N), Space ~ O(N) 先找最左节点，然后一层层往上返回，没返回一层节点，要进入其右子树遍历（重复该过程）。 注意：程序结构和pre-order几乎是一致的，仅是 list.add(curr.val) 的位置不同。

// left-root-right
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null)   return list;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null) {
        stack.push(curr);
        curr = curr.left;
    }

    while (!stack.isEmpty()) {
        curr = stack.pop();
        list.add(curr.val);
        curr = curr.right;
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
    }
    return list;
}

1. Morris Inorder Traversal: Time ~ O(N), Space ~ O(1) 改变Tree的结构，将node下最右节点连接node的parent，这样可以自动返回上层。 参见：wikipedia // Morris inorder traversal: Space ~ O(1)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    TreeNode curr = root;

    while (curr != null) {
        if (curr.left != null) {        // if curr has left children
            TreeNode prev = curr.left;
            while (prev.right != null && prev.right != curr) {
                prev = prev.right;      // find the rightmost node in curr's left subtree
            }
            if (prev.right == null) {   // set right to successor, and go to left
                prev.right = curr;
                curr = curr.left;
            } else {                    // visit and revert the change, and go to right
                prev.right = null;
                list.add(curr.val);
                curr = curr.right;
            }
        } else {                        // if curr doesn't have left child, go to right
            list.add(curr.val);
            curr = curr.right;
        }
    }
    return list;
}

Level-order: Top-Down

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7}, return its level order traversal as: [ [3], [9,20], [15,7] ] 3 / \ 9 20 / \ 15 7

Solution

BFS: Time ~ O(N), Space ~ O(N) 用一个Queue，在遍历每一个节点的时候，将val加入List，并将其左右节点加入Queue中。 区分level：在每层结束后queue.add(null)，接下来当 curr == null，表明到达该level的尾部。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> listSet = new ArrayList<List<Integer>>();
    if (root == null)   return listSet;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    queue.add(null);    // flag of end-of-level

    while (!queue.isEmpty()) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode curr = queue.poll();
        while (curr != null) {
            list.add(curr.val);
            if (curr.left != null)  queue.add(curr.left);
            if (curr.right != null) queue.add(curr.right);
            curr = queue.poll();
        }
        listSet.add(list);
        if (!queue.isEmpty())   queue.add(null);
    }
    return listSet;
}

Level-order: Bottom-Up

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree {3,9,20,#,#,15,7}, return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]

Solution

BFS: Time ~ O(N), Space ~ O(N) 先用Top-down level-order，再将结果反转。

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> listSet = new ArrayList<List<Integer>>();
    if (root == null)   return listSet;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    queue.add(null);

    // top-down levelorder traversal
    while (!queue.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        TreeNode curr = queue.poll();
        while (curr != null) {
            list.add(curr.val);
            if (curr.left != null)  queue.add(curr.left);
            if (curr.right != null) queue.add(curr.right);
            curr = queue.poll();
        }
        listSet.add(list);
        if (!queue.isEmpty())   queue.add(null);
    }

    // reverse the top-down levelorder traversal
    Collections.reverse(listSet);
    return listSet;
}

Level-order: Zigzag

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7}, return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

Solution

BFS: Time ~ O(N), Space ~ O(N) 用两个Stack，stack存放当前行的node，stackTmp存放下一行的node。 另用一个boolean值记录奇偶行，由此决定放入左右node的顺序： 当oddLevel = true，先右后左； 当oddLevel = false，先左后右。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> listSet = new ArrayList<List<Integer>>();
    if (root == null)   return listSet;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    boolean oddLevel = false; // false - 0,2,4,...,levels

    while (!stack.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stackTmp = new Stack<>();
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(curr.val);
            if (oddLevel) {
                if (curr.right != null) stackTmp.push(curr.right);
                if (curr.left != null)  stackTmp.push(curr.left);
            } else {
                if (curr.left != null)  stackTmp.push(curr.left);
                if (curr.right != null) stackTmp.push(curr.right);
            }
        }
        listSet.add(list);
        stack = stackTmp;
        oddLevel = !oddLevel;
    }
    return listSet;
}