LeetCode | Binary Tree Inorder Traversal

題目

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

老套路，遞歸（解法1）和非遞歸（解法2）各來一遍。

解法1

import java.util.ArrayList;

public class BinaryTreeInorderTraversal {
	public ArrayList inorderTraversal(TreeNode root) {
		ArrayList list = new ArrayList();
		solve(root, list);
		return list;
	}

	private void solve(TreeNode root, ArrayList list) {
		if (root == null) {
			return;
		}
		solve(root.left, list);
		list.add(root.val);
		solve(root.right, list);
	}
}

import java.util.ArrayList;
import java.util.Stack;

public class BinaryTreeInorderTraversal {
	public ArrayList inorderTraversal(TreeNode root) {
		ArrayList list = new ArrayList();
		Stack stack = new Stack();
		while (root != null) {
			stack.push(root);
			root = root.left;
		}
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			list.add(node.val);
			TreeNode right = node.right;
			while (right != null) {
				stack.add(right);
				right = right.left;
			}
		}
		return list;
	}
}