題目描述

給定一個 N 叉樹脖岛，返回其節(jié)點值的后序遍歷菱鸥。
相關(guān)話題：?樹????難度：?簡單

例如，給定一個 3叉樹 :

返回其后序遍歷: [5,6,3,2,4,1].
說明: 遞歸法很簡單，你可以使用迭代法完成此題嗎?

• 解法1
  使用遞歸的方法先遍歷當前節(jié)點的所有children節(jié)點压真，遍歷完后處理當前節(jié)點。

    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    public void postorder(Node root, List<Integer> res){
        if(root == null) return;
        //遍歷當前節(jié)點的children
        for(Node x : root.children){
            postorder(x, res); 
        }
        //遍歷完children后蘑险，處理當前節(jié)點
         res.add(root.val);
    }

• 解法2
  迭代方式的解題思路和leetcode 145題類似滴肿，同樣用到兩個棧，一個協(xié)助以“中->右->左”遍歷樹佃迄，一個保存遍歷的結(jié)果泼差。
• 初始狀態(tài)下贵少，stack1保存了根節(jié)點(為了統(tǒng)一操作，包裝到list)堆缘。
• while循環(huán)內(nèi)滔灶，彈出stack1中的List對象（也就是子節(jié)點的集合），先處理最后一個節(jié)點(Node x = list.remove(list.size()-1);stack2.push(x);)吼肥，然后如果list不為空的話录平，將其壓回到stack1中，并將當前節(jié)點(最右的節(jié)點)的子節(jié)點集合壓到stack1中缀皱。
• stack1為空時斗这，遍歷結(jié)束。
  以上就是“中->右->左”的遍歷過程啤斗。

public List<Integer> postorder(Node root) {
        if(root == null) return new ArrayList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        //保存剩余未遍歷子節(jié)點(左)
        Stack<List<Node>> stack1 = new Stack<>();
        //保存結(jié)果
        Stack<Node> stack2 = new Stack<>();
        List<Node> tmp = new ArrayList<Node>();
        tmp.add(root);
        stack1.push(tmp);
        while(!stack1.isEmpty()){
            List<Node> list = stack1.pop();
            Node x = list.remove(list.size()-1);
            stack2.push(x);
            if(!list.isEmpty()){
                stack1.push(list);
            }
            if(!x.children.isEmpty()){
                stack1.push(x.children);
            }
        }
        while(!stack2.isEmpty()){
            res.add(stack2.pop().val);
        }
        return res;
    }