題目描述
給定一個二叉樹，返回它的 后序 遍歷冤吨。
相關(guān)話題：?棧、樹????難度：?困難
示例
進(jìn)階: 遞歸算法很簡單凤跑，你可以通過迭代算法完成嗎叛复？
-
解法1
二叉樹的題用遞歸解法是相當(dāng)簡潔的，后序遍歷的話就先處理左子樹再處理右子樹咖耘，最后處理當(dāng)前節(jié)點(diǎn)撬码。
二叉樹的遞歸遍歷中呜笑，每個節(jié)點(diǎn)都會被經(jīng)歷三次（如上圖所示），所謂的前中后序遍歷其實(shí)就看你在哪一次經(jīng)過當(dāng)前節(jié)點(diǎn)的時候?qū)?jié)點(diǎn)進(jìn)行操作凰慈。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorderTraversal(res,root);
return res;
}
public void postorderTraversal(List<Integer> res,
TreeNode root){
if(root == null) return;
postorderTraversal(res,root.left);
postorderTraversal(res,root.right);
res.add(root.val);
}
-
解法2
這道題的難度系數(shù)之所以定義為困難驼鹅，就是需要用迭代的方式來做，就要將遞歸版本改為用棧記錄以前的信息豺型。
既然是后序遍歷买乃，則需要遵循"左子樹->右子樹->當(dāng)前節(jié)點(diǎn)"的訪問順序。
思路：后序遍歷的非遞歸版本是三種遍歷中最難的肴焊。這里我們使用兩個棧來協(xié)助完成二叉樹的遍歷操作碉咆。
不難發(fā)現(xiàn)疫铜，如果我們以“中->右->左”的順序遍歷二叉樹，將結(jié)果壓進(jìn)棧中，彈棧的時候順序就是“左->右->中”顽馋，也就是后序遍歷的結(jié)果了幌羞。
而“中->右->左”的遍歷順序和先序遍歷很像（先序遍歷是“中->左->右”） - 用stack1協(xié)助以“中->右->左”的順序遍歷二叉樹属桦，將結(jié)果保存到stack2中
- 依次彈出stack2中的元素即為二叉樹的后序遍歷結(jié)果
所以整個過程就是，彈出stack1棧頂節(jié)點(diǎn)(也就是訪問當(dāng)前節(jié)點(diǎn))聂宾，并將其壓進(jìn)stack2中系谐，如果當(dāng)前節(jié)點(diǎn)有左子樹，壓進(jìn)stack1鄙煤，如果當(dāng)前節(jié)點(diǎn)有右子樹茶袒，壓進(jìn)stack1。(根據(jù)棧FILO的特點(diǎn)乾巧，遍歷順序就是“中->右->左”)，最后將stack2中的元素全部彈出即為結(jié)果咳胃。
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return new ArrayList<Integer>();
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack1.push(root);
while(!stack1.isEmpty()){
TreeNode x = stack1.pop();
stack2.push(x);
if(x.left != null){
stack1.push(x.left);
}
if(x.right != null){
stack1.push(x.right);
}
}
while(!stack2.isEmpty()){
res.add(stack2.pop().val);
}
return res;
}
