N叉树的后序遍历（JAVA）【递归 && 迭代】

N叉树的后序遍历

题目描述

给定一个 N 叉树，返回其节点值的后序遍历。

图示

题解一（java递归）

class Solution {
    List<Integer> list;
    public List<Integer> postorder(Node root) {
        //递归
        list = new ArrayList<>();
        //递归根节点
        order(root);
        return list;

    }
    public void order(Node root)
    {
        if(root == null){
            //如果节点为空，终止递归
            return;
        }
        //遍历该根节点的所有子节点
        for(Node child : root.children){
            order(child);
        }
        //等到遍历终止时，此时节点的值为底层节点的值
        //将该节点的值直接添加到列表中即可
        list.add(root.val);
    }
}
           

Tips

• 1>.递归函数中，我们用 for循环 实现了广度优先搜索，即先遍历同一深度下的所有节点
• 2>.在定义列表时，不应在函数中定义，应该在全局中定义，因为不同的函数中都会用到 list
• 3>.另外，在向链表中添加值的时候，应该在 for 循环结束后再添加，因为 for 循环中的 root 为当前 root 的根节点，不是我们需要的值。

题解二（java迭代）

/迭代法
class Solution {
    List<Integer> list = new ArrayList<>();
    Deque<Node> stack = new LinkedList<>();
    public List<Integer> postorder(Node root) {
        order(root);
        return list;
    }
    public void order(Node root){
        if(root == null){
            return;
        }
        stack.push(root);
        Node current;
        while(!stack.isEmpty()){
            current = stack.pop();
            list.add(current.val);
            for(Node child : current.children){
                stack.push(child);
            }
        }
        Collections.reverse(list);
    }
}
           

详解

• 1>.首先，我们将根节点压入栈中。
• 2>.定义一个 current 节点来表示当前栈中最上面的节点
• 3>.设置遍历的终止条件为 栈为空
• 4>.如果栈不为空，栈中最上面的节点出栈，记为 current ，并把 current 节点的值添加入 list 中。
• 5>.然后遍历该节点的全部子节点，全部按照顺序压入栈中，然后再按照入栈的顺序 出栈，加入列表中…
• 6>.最后将列表反转即可

Tips

-1>.列表也应该在遍历都结束后再反转

拓展

• Deque 堆栈(双端队列)
• 1>.peek 获取栈顶元素
• 2>.pop 删除栈顶元素
• 3>.push 向栈底插入元素

声明

• 原作者：E.L.E
• <著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处>
• <欢迎大家评论>