刷题小记 (17) LeetCode 590 N叉树的后续遍历

LeetCode 590

2020.8.15

我的通过代码

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<Integer>();
        traverse(root,list);
        return list;
    }

    void traverse(Node root, List<Integer> list) {
        if(root==null) return;
        if(root.children.size()==0) {
            list.add(root.val); return;
        } else {
            for(int i=0;i<root.children.size();i++) {
                traverse(root.children.get(i),list);
            }
            list.add(root.val);
        }
    }
}
           

这种方法是通过递归来完成的，比较好想到。

当然，题目本身要求咱们试着用迭代来完成，这就比较有意思了。

先来看看题目：

二叉树的这三种遍历我们会首选递归，是因为递归可以通过一层层的调用函数，从头开始，直达我们需要处理的节点，开始处理，再一层层往外走，这十分贴合我们人的思考方式。

而迭代需要从头开始处理，一般而言没有回头的机会，这就意味着我们走到一个节点旁边的时候就要处理它了，这其实也和后序遍历本身的原理相违背。

但是，机器是死的，人是活的，

如果我们把上面那颗N叉树逆转（Reverse）一下

对它进行从左至右的广度遍历，那么我们会得到这样一个集合

这好像刚好和我们要的答案是镜像的，挺好。

这样一来我们只需要对原来的树从右往左做广度遍历即可，代码如下：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    List<Integer> list = new ArrayList<Integer>();
    Stack<Node> stack = new Stack<Node>();
    public List<Integer> postorder(Node root) {
        if(root==null) return list;
        Node temp = root;
        stack.push(temp);
        while(stack.size()>0) {
            temp = stack.pop();
            list.add(temp.val);
            for(int i=0;i<temp.children.size();i++) {
                stack.push(temp.children.get(i));
            }

        }
        Collections.reverse(list);

        return list;
    }
}
           

从右往左的广度遍历只需要将一个节点的孩子们依次入栈即可。

最后的逆转使用一个reverse函数来完成。