本題考察的二叉樹的后序遍歷
題目描述
給定一個二叉樹，返回它的 后序 遍歷错妖。
示例:
輸入: [1,null,2,3]
1
2
/
3
輸出: [3,2,1]
進階: 遞歸算法很簡單绿鸣，你可以通過迭代算法完成嗎？
題目思考
本題考察的是基礎(chǔ)的二叉樹遍歷暂氯。我們應(yīng)該把二叉樹的各種遍歷（前序潮模，后序，中序痴施，層序）掌握得很清楚擎厢。二叉樹的遍歷無非就兩種方法：遞歸和隊列/棧。好好總結(jié)一下辣吃，收獲會很多动遭。
代碼
遞歸方法
class Solution {
List<Integer> res=new ArrayList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
loop(root);
return res;
}
public void loop(TreeNode node){
if(node==null)
return;
loop(node.left);
loop(node.right);
res.add(node.val);
}
}
棧方法
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<Integer>();
if(root==null)
return res;
Stack<TreeNode> stack=new Stack();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp=stack.peek();
if(temp.left==null&&temp.right==null){
stack.pop();
res.add(temp.val);
}else if(temp.left!=null){
TreeNode left=temp.left;
temp.left=null;
stack.push(left);
}else if(temp.right!=null){
TreeNode right=temp.right;
temp.right=null;
stack.push(right);
}
}
return res;
}
}
