Home Computer Science Java Algorithm

67 · Binary Tree Inorder Traversal - LintCode

# Description

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

# Example

Example 1:

Input:

binary tree = {1,2,3}

Output:

[2,1,3]

# Solution

  1. 先把左邊的孩子全都放到 stack 裡
  2. peek():
    1. if node.right == null，先 pop 掉
      1. 看一下現在的 node 和現在 stack.peek 的 right 孩子是不是一樣；如果一樣說明已經訪問過了，把它也 pop 掉；
    2. if node.right != null
      1. 可以往右樹看，再把右樹的左孩子全都加到棧裡。
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null){
            stack.push(root);
            root = root.left;
        }
        while (!stack.isEmpty()){
            TreeNode node = stack.peek();
            result.add(node.val);
            
            if (node.right == null){
                    node = stack.pop();
                while (!stack.isEmpty() && stack.peek().right == node){
                     node = stack.pop();
                }
            }
            else { // when node.right != null
                node = node.right;
                while (node != null){
                    stack.push(node);
                    node = node.left;
                }
            }
        }
        return result;
    }
}