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的右子树。

这里其实有一个中间步骤，就是pop出1来之后，root被定义成了1的right kid，然而1并没有right kid。但是这是stack里面还有[8, 3]。所以下一次运行L9的while时，我们会跳过L10-L12直接从stack里面在pop出3来。

然后又是用while root将最以3为root的tree左边的一条臂全都推入栈中。

所以这个解法的巧妙之处就在于我们其实每次从stack里面pop出一个node时，都试图将root挪到他的右子树的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.left13             root = stack.pop()14             ans.append(root.val)15             root = root.right16         return ans17