144. Binary Tree Preorder Traversal && 145. Binary Tree Postorder Traversal

非递归形式的前中后序遍历，有一篇文章说得比较详细http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

 

 

 PreOrder：

public class Solution { List<Integer> rst = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); public List<Integer> preorderTraversal(TreeNode root) { if(root == null) return rst; // 先一直往左边走，同时把right child保存到stack，当左边遍历完了，就一个个弹出栈 while(root != null) { // 先一直往左走 while(root != null) { rst.add(root.val); stack.push(root); root = root.left; } // 往右 while(!stack.isEmpty()) { root = stack.pop(); root = root.right; if(root != null) break; } } return rst; } }

可以写简单点

class Solution: def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ st=[] res=[] while st or root: while root: st.append(root) root=root.left if st: t = st.pop() res.append(t.val) root = t.right return res

如果是多叉树，就得一次性把所有的child加到stack里，注意不同的遍历对应加的原始数组还是resverse

 

 

 

 

后序遍历在Discuss里有一个解法比较简单，描述如下，简单修改PreOrder的代码即可：

pre-order traversal is root-left-right, and post order is left-right-root. modify the code

 for pre-order to make it root-right-left, and then reverse the output so that we can get

 left-right-root .

 

public class Solution { List<Integer> rst = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); public List<Integer> postorderTraversal(TreeNode root) { if(root == null) return rst; while(root != null) { while(root != null) { rst.add(root.val); stack.push(root); root = root.right; } while(!stack.isEmpty()) { root = stack.pop(); root = root.left; if(root != null) break; } } Collections.reverse(rst); return rst; } }