Leetcode 590：N 叉树后序遍历

介绍

  • 在这篇文章中，我们将解决 Leetcode 590 题，哪道题是练习树数据结构的好题
  • 我们还将研究该问题的基于堆栈stack的解决方案以及递归解决方案。

问题陈述

  • 我们已经给定了 N 叉树，我们需要返回它的节点值的后序遍历。
  • 表示的输入树具有空值，基本上描述了子级与父级的分离。

例子

  • 在此示例中，我们可以看到输入有 null，这意味着给定的父级有子级，并且其由 null 分隔。
  • 后序遍历意味着我们首先覆盖左子节点，然后覆盖右子节点，但由于我们的树是 n 元树，这意味着我们将从左到右进行后序遍历。
  • 所以后序将是左 -> 右子节点 + 父节点。
  • 输入：[1,null,3,2,4,null,5,6]
  • 应该输出：[ [5,6,3], [ 2] , [4] , 1]

完整的递归代码：

class Solution {
    List<Integer> result = new ArrayList<>();
     
    public List<Integer> postorder(Node root) {
        if(root==null) return result;
        sol1(root);
        result.add(root.val);
        return result;
    }
 
 
private void sol1(Node root){
        if(root.children==null){
            return;
        }
         
        for(Node node:root.children){
            sol1(node);
            result.add(node.val);
        }
}
}

思路：
我们将首先遍历每个子节点，然后进行递归调用，直到到达该节点没有任何子节点的阶段。

一旦我们有了这种情况，我们就可以返回我们的调用并将该节点添加到我们的结果中。

private void sol1(Node root){
        if(root.children==null){
            return;
        }
         
        for(Node node:root.children){
            sol1(node);
            result.add(node.val);
        }
}

一旦我们完成了所有子节点的遍历，现在我们终于可以将根节点添加到列表中了。

        sol1(root);
        result.add(root.val);
        return result;


还可以使用基于堆栈的方法在遍历节点时将每个子节点添加到堆栈中。

class Solution {
    List<Integer> result = new ArrayList<>();
     
    public List<Integer> postorder(Node root) {
        sol2(root);
        return result;
    }
 
 
     private void sol2(Node root){
        if(root.children==null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
         Node curr = stack.pop();
         result.add(curr.val);
         for(Node node: curr.children){
           stack.push(node);  
         }
        }
         
        Collections.reverse(result); 
    }
}

  • 这里要记住的一件事是，对于堆栈，我们从左向右移动，因此右侧将首先弹出并添加到列表中，作为与我们想要的第一个对比。
  • 我们希望首先处决左孩子。
  • 因此我们需要在最后反转结果列表：Collections.reverse(result);

复杂

  • 时间复杂度：O(N)，其中 N 是树中的节点数
  • 空间复杂度：O(H)，其中 H 是树的高度

结论
  • 在本文中，我们解决了 Leetcode 590 解决方案，它帮助我们理解 n 叉树以及如何按后序遍历它。
  • 我们还讨论了基于堆栈的解决方案作为变体。