[LindCode] Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

Given a binary tree, return the?postorder?traversal of its nodes' values.

Example

Given binary tree?{1,#,2,3},

   1\2/3

?

return?[3,2,1].

Challenge

Can you do it without recursion?

?

SOLUTION 1:

recursion：

分治法解決之，非常直觀，非常好理解，左子樹加到result里，右子樹加入result里，再把root加到result里。

看代碼：

public class Solution {/*** @param root: The root of binary tree.* @return: Postorder in ArrayList which contains node values.*/public ArrayList<Integer> postorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();if (root == null){return result;}ArrayList<Integer> left = postorderTraversal(root.left);ArrayList<Integer> right = postorderTraversal(root.right);result.addAll(left);result.addAll(right);result.add(root.val);return result;}
}

?

SOLUTION 2：

no-recursion：

　　　　　　　　　　　　　　　　　　　　　　　　1

　　　　　　　　　　　　　　　　　　　　　　　/　　\

　　　　　　　　　　　　　　　　　　　　　　2　　　　3

　　　　　　　　　　　　　　　　　　　　　　　　　　/　\

　　　　　　　　　　　　　　　　　　　　　　　　　 4　　5

?假設一個樹是上面這個樣子，開始分析：

1，將根節點入棧，并將根節點的孩子入棧，入棧順序為：先入右孩子，再入左孩子，順序不能錯。因為這樣在彈棧時的順序就是后序遍歷的順序了。如果左孩子還有左孩子或者右孩子，那么繼續按先右后左的順序入棧。那么上面這棵樹開始的入棧順序是：1，3，2。由于2不存在左右孩子，停止入棧。

2，由于2沒有左右孩子，遍歷2并將2彈出，同時使用prev記錄下2這個節點。

3，2出棧后，棧為{1，3}，此時3在棧頂，由于3存在左右孩子，按順序入棧，此時棧為{1，3，5，4}。

4，將4和5遍歷并出棧，此時prev指向5，棧為{1，3}。prev的作用是什么呢？用來判斷prev是否為棧頂元素的孩子，如果是，則說明子樹的孩子已經遍歷完成，需要遍歷樹根了。以上樹為例：4和5出棧后，prev指向5，而5是棧頂元素3的孩子，說明孩子已經遍歷完畢，則遍歷3然后彈出3即可，即完成了子樹{3，4，5}的后序遍歷。

5，此時棧為{1}，為樹根，而左右子樹都遍歷完了，最后遍歷樹根并彈出即可。

以上方法取自：大神?http://www.cnblogs.com/zuoyuan/p/3720846.html 講的非常詳細。

?

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: Postorder in ArrayList which contains node values.*/public ArrayList<Integer> postorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode pre = null;while (root != null || !stack.isEmpty()){if (root != null){stack.push(root);root = root.left;} else if (stack.peek().right != pre){root = stack.peek().right;pre = null;} else {pre = stack.pop();result.add(pre.val);}}return result;}
}

?