給定一個(gè)二叉樹余蟹，返回它的 后序 遍歷。
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [3,2,1]
非遞歸(迭代):
后序遍歷遞歸定義：先左子樹子刮，后右子樹威酒，再根節(jié)點(diǎn)窑睁。
后序遍歷的難點(diǎn)在于：需要判斷上次訪問(wèn)的節(jié)點(diǎn)是位于左子樹，還是右子樹葵孤。
若是位于左子樹担钮，則需跳過(guò)根節(jié)點(diǎn)，先進(jìn)入右子樹尤仍，再回頭訪問(wèn)根節(jié)點(diǎn)箫津；
若是位于右子樹，則直接訪問(wèn)根節(jié)點(diǎn)宰啦。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) return list;
TreeNode cur = root;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
//把currentNode移到左子樹的最下邊
while(cur != null){
stack.push(cur);
cur = cur.left;
}
while(!stack.isEmpty()){
cur = stack.pop();
//一個(gè)根結(jié)點(diǎn)被訪問(wèn)的前提是：無(wú)右子樹或右子樹已被訪問(wèn)過(guò)
if(cur.right == null || pre == cur.right){
//訪問(wèn)
list.add(cur.val);
//修改最近被訪問(wèn)的節(jié)點(diǎn)
pre = cur;
}else{
//根結(jié)點(diǎn)再次入棧
stack.push(cur);
//進(jìn)入右子樹苏遥，且可以肯定右子樹一定不為空
cur = cur.right;
while(cur != null){
//再次走到右子樹的最左邊
stack.push(cur);
cur = cur.left;
}
}
}
return list;
}
}
遞歸：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
postorder(root);
return list;
}
public void postorder(TreeNode root){
if(root != null){
postorder(root.left);
postorder(root.right);
list.add(root.val);
}
}
}
