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?
题目大意：中序遍历一个二叉树，递归的方案太low，用迭代的方式来写？
解题思路：不用递归，那就自己实现栈呗
1、首先节点入栈，处理当前节点左孩子，并且压入栈，当左节点非空，循环遍历；
2、找到第一个左孩子为空的节点，将此节点出栈，将节点值加入结果链表，并把当前节点设为右孩子；
3、循环到栈为空。
1 public List<Integer> inorderTraversal(TreeNode root) { 2 List<Integer> res = new ArrayList<>(); 3 Stack<TreeNode> stack = new Stack<>(); 4 TreeNode curr = root; 5 while (curr != null || !stack.isEmpty()) { 6 while (curr != null) { 7 stack.add(curr); 8 curr = curr.left; 9 } 10 curr = stack.pop(); 11 res.add(curr.val); 12 curr = curr.right; 13 } 14 return res; 15 }
Binary Tree Inorder Traversal ——LeetCode
原文：http://www.cnblogs.com/aboutblank/p/4451869.html