Given a binary tree, return the inorder traversal
of its nodes' values.
样例
Given binary tree {1,#,2,3}
,
1 \ 2 / 3
return [1,3,2]
.
挑战
Can you do it without recursion?
/** * 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: The root of binary tree. * @return: Inorder in ArrayList which contains node values. */ public static ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> tree = new ArrayList<Integer>(); Stack<TreeNode> s = new Stack<TreeNode>(); while (root != null) { if (root.left == null) { tree.add(root.val); if (root.right != null) { TreeNode r = root.right; root.right = null; root = r; } else if (!s.isEmpty()) root = s.pop(); else root = null; } else if (root.left != null) { TreeNode l = root.left; root.left = null; s.push(root); root = l; } } return tree; } }