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?
要求使用非递归解法，代码如下：
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if(root == null) return list; Stack<TreeNode> nodes = new Stack<TreeNode>(); nodes.add(root); while(!nodes.isEmpty()) { while(nodes.peek().left != null) { nodes.add(nodes.peek().left); } TreeNode curr = nodes.pop(); while(curr.right == null) { list.add(curr.val); if(nodes.isEmpty()) return list; curr = nodes.pop(); } list.add(curr.val); nodes.push(curr.right); } return list; }
LeetCode-94 Binary Tree Inorder Traversal
原文：http://www.cnblogs.com/linxiong/p/4240456.html