题目
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]
.
Note: Recursive solution is trivial, could you do it iteratively?
链接:
5/10/2017
感觉大家都是默默的记住了这个算法,并没有很多的解释为什么这样子。。。
我来尝试一下:
打印左子树时候,parent还是在Stack里,打印右子树时候,parent不在stack里。
这个算法是在pop出来的时候add to ret,所以因为处理right时候,parent不需要在stack。处理左子树时候,还没有轮到parent,所以parent需要在Stack里。
是不是有这个规律?只要是parent值在当前值之后处理,parent就应该在stack里,而如果parent在当前值处理之前已处理完,parent就不在stack里。
1 public class Solution { 2 public ListinorderTraversal(TreeNode root) { 3 List ret = new ArrayList (); 4 if (root == null) return ret; 5 6 Stack stack = new Stack (); 7 TreeNode current = root; 8 // when processing left, parent is in stack 9 // when processing right, parent is no longer in stack10 while (current != null || !stack.empty()) {11 while (current != null) {12 stack.push(current);13 current = current.left;14 }15 current = stack.pop();16 ret.add(current.val);17 current = current.right;18 }19 return ret;20 }21 }
更多讨论