Menu

Subscribe

LeetCode 94 : Binary Tree Inorder Traversal

on Code

Given a binary tree, return the inorder traversal of its nodes' values.

For example: Given binary tree

 1
  \
   2
  /
 3

return [1,3,2]

Initial Though

這題如果用 recursive 的話十分簡單，但是如果要用 iterative 作的話就不是這麼容易，最主要的原因是你無法用 call recursive 的順序來決定你 output value 的順序。

Guide

首先你需要有一個 Stack 來倒序記錄，由於 Inorder 是 中->左->右 ，所以必須有一個方式來記錄走到最左之間的所有 Node 。 所以作法就是每次 iteration 先看 Stack Q 的 top， 如果他有左子孫的話，就把它加上去。所以我們會走到樹的最左邊，並且 Stack Q 到目前為止的 Node 。 此時 top 就沒有左子孫，因為此時是作 Inorder ， 所以這時候我們要先把 top 的 value 輸出 。 並判斷他有沒有右子孫，如果有的話就要加到 Stack Q 上面。 這裡有一個很重要的步驟就是，要能標記哪些 Node 已經輸出，這樣才不會重複輸出， 所以在把 top 的 value 輸出後，除了要 removeFirst，並且把 values 設成 Integer.MIN_VALUE 來標示已經輸出了。如此做到 Stack Q 為空的時候後停止。以下就用跟上面一樣的例子，來看 Stack Q 在整個演算法之中的情況，應該就會比較好理解。

[ ]    [ ]    [1]    [1]    [1]   [1,3] [1,3,2]
| |    | |    | |    | |    | |    | |    | |
| | -> | | -> | | -> | | -> |3| -> | | -> | |
| |    |1|    | |    |2|    |2|    |2|    | |
|_|    |_|    |_|    |_|    |_|    |_|    |_|
        1      2      2      3      4      5
  1. put root 1
  2. top node 1 has no left child -> pop and output value, top node 1 has right child -> put right child 2
  3. top node 2 has left child -> put left child 3 and skip the rest
  4. top node 3 has no left child -> pop and output value, top node 3 has no right child then do nothing
  5. top node 2 has no left child -> pop and output value, top node 2 has no right child then do nothing

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<Integer> inorderTraversal(TreeNode root) {
        LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
        List<Integer> result = new ArrayList<Integer>();
        if(root!=null)
            Q.addFirst(root);
        while(!Q.isEmpty()){
           TreeNode iter = Q.get(0);
            if(iter.left != null ){
                if(iter.left.val != Integer.MIN_VALUE){
                    Q.addFirst(iter.left);
                    continue;
                }
            }
            TreeNode output = Q.removeFirst();
            result.add(output.val);
            output.val = Integer.MIN_VALUE;
            if(iter.right != null){
                Q.addFirst(iter.right);
            }
        }
        return result;
    }
}

Postorder

如此掌握 Inorder 的作法後，用類似的模式也可以做到 Postorder。

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
        List<Integer> result = new ArrayList<Integer>();
        if(root!=null)
            Q.addFirst(root);
        while(!Q.isEmpty()){
           TreeNode iter = Q.get(0);
            if(iter.left != null ){
                if(iter.left.val != Integer.MIN_VALUE){
                    Q.addFirst(iter.left);
                    continue;
                }
            }
            if(iter.right != null){
                if(iter.right.val != Integer.MIN_VALUE){
                    Q.addFirst(iter.right);
                    continue;
                }
            }
            TreeNode output = Q.removeFirst();
            result.add(output.val);
            output.val = Integer.MIN_VALUE;
        }
        return result;
    }
}