Given a binary tree, return the inorder traversal of its nodes‘ values.
For example:
Given binary tree [1,null,2,3],
1
2
/
3
return [1,3,2].
本题如果用recursive的方法非常简单。这里主要考察用iterative的方法求解。例如： [1,3,4,6,7,8,10,13,14]
从8开始依次将8,3,1 push入栈。这时root=None，每当root=None时就从stack里pop一个node出来。并将root定义成3的右子树。然后又是用while root将最左边的一条臂全都推入栈中。
1 class Solution(object): 2 def inorderTraversal(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: List[int] 6 """ 7 ans = [] 8 stack = [] 9 while stack or root: 10 while root: 11 stack.append(root) 12 root = root.left 13 root = stack.pop() 14 ans.append(root.val) 15 root = root.right 16 return ans 17
Leetcode 94. Binary Tree Inorder Traversal
原文：http://www.cnblogs.com/lettuan/p/6248118.html