Leetcode每日打卡------二叉樹的後序周遊

文章目錄

• • 二叉樹的後序周遊

二叉樹的後序周遊

給定一個二叉樹，傳回它的 後序 周遊。

示例:

輸入: [1,null,2,3]  
   1
    \
     2
    /
   3 

輸出: [3,2,1]
           

• 思路一：這一題定義為中等題，如果用遞歸的話，這應該算是一個簡單題，先給出一個遞歸的寫法，左右根

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);

        return list;
    }
}
           

• 思路二：修改前序周遊代碼中，節點寫入結果連結清單的代碼，将插入隊尾修改為插入隊首；修改前序周遊代碼中，每次先檢視左節點再檢視右節點的邏輯，變為先檢視右節點再檢視左節點
• 或者按照左右根順序，維護兩個棧，第一個棧先左子節點，再放右子節點，然後每次彈出一個元素，放入到第二個棧中。最後第二個棧依次彈出每個元素。

public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<Integer>();
        
        TreeNode node = root;
        List<Integer> ret = new ArrayList<Integer>();
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (node.right == null || 
                    (ret.size() != 0 && ret.get(ret.size() - 1).equals(node.right.val)) ) {
                ret.add(node.val);
                node = null;
            }  else {
                stack.push(node);
                node = node.right;
            }
        }
        return ret;
    }

           

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<Integer> stack2 = new Stack<Integer>();
        stack1.push(root);
        while(!stack1.isEmpty()){
            TreeNode temp = stack1.pop();
            if(temp!=null){
                stack2.push(temp.val);
                stack1.push(temp.left);
                stack1.push(temp.right);
            }
        }
        List<Integer> results = new ArrayList<Integer>();
        while(!stack2.isEmpty()){
            results.add(stack2.pop());
        }
        return results;
    }
}