102 Binary Tree Level Order Traversal

Questions:

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},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Analysis：

BFS算法，用队列。

Concept:

https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

广度优先搜索算法（英语：Breadth-First-Search），又译作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

实现方法

• 首先将根节点放入队列中。
• 从队列中取出第一个节点，并检验它是否为目标。
  • 如果找到目标，则结束搜寻并回传结果。
  • 否则将它所有尚未检验过的直接子节点加入队列中。
• 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。 重复步骤2。

William的all kinds of 解法： http://wlcoding.blogspot.com/2015/03/binary-tree-traversal-preorder.html?view=sidebar

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        // Queue is an abstract class, cannot implement as Queue<TreeNode> nodes = new Queue<TreeNode>()
        // must be like LinkedList<TreeNode>(); or DelayQueue....
        Queue<TreeNode> nodes = new LinkedList<TreeNode>();
        TreeNode parent = root;
        if (root == null) {
            return lists;
        }
        nodes.add(parent);

        int count = 0;
        int num = 1;
        while (nodes.peek() != null) {
            lists.add(new ArrayList<Integer>());
            for (int i = 0; i < num; i++) {
                // I think what queue removes is the reference, not the node in the tree.
                parent = nodes.remove();
                lists.get(lists.size() - 1).add(parent.val);
                if (parent.left != null) {
                    nodes.add(parent.left);
                    count++;
                }
                if (parent.right != null) {
                    nodes.add(parent.right);
                    count++;
                }
            }
            // here, if use only count, the count cannot return zero, so it needs an temp
            // to store the iterate value.
            num = count;
            count = 0;
        }
        return lists;
    }
}

Updated (12.19.15)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private List<List<Integer>> list;
    private Queue<TreeNode> queue;
    public List<List<Integer>> levelOrder(TreeNode root) {
        list = new ArrayList<List<Integer>>();
        queue = new LinkedList<TreeNode>();
        if (root == null) {
            return list;
        }
        helper(root);
        return list;
    }
    private void helper(TreeNode root) {
        queue.add(root);
        int count = 1;
        int num = count;
        while (queue.peek() != null) {
            list.add(new ArrayList<Integer>());
            count = 0;
            while (num > 0) {
                TreeNode node = queue.peek();
                if (node.left != null) {
                    queue.add(node.left);
                    count++;
                }
                if (node.right != null) {
                    queue.add(node.right);
                    count++;
                }
                list.get(list.size() - 1).add(queue.poll().val);
                num--;
            }
            num = count;
        }
    }
}

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