【算法题解】44. N 叉树的前序遍历（递归 + 迭代）

- 日理万妓 2024-03-17 12:05 6阅读 0赞

> 这是一道 **简单** 题  
>   
> https://leetcode.cn/problems/n-ary-tree-preorder-traversal/

### 题目 ###

给定一个 `n` 叉树的根节点 `root` ，返回 其节点值的 **前序遍历** 。

`n` 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 `null` 分隔（请参见示例）。

**示例 1：**  
![4817762f45a7a63d2682b1851b35560c.png][]

输入：root = [1,null,3,2,4,null,5,6] 
    输出：[1,3,5,6,2,4]

**示例 2：**  
![badb3af3fcaedd038d6f1bb4e7ad95fb.png][]

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 
    输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

**提示：**

*  节点总数在范围  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\] 内
 *  $ 0 <= Node.val <= 10^4 $
 *  `n` 叉树的高度小于或等于 `1000`

**进阶：**递归法很简单，你可以使用迭代法完成此题吗?

--------------------

### 递归解法 ###

**递归函数：**将当前节点值放入答案，然后从左到右递归所有子节点。

**边界条件：**节点为空，直接返回。

##### Java 代码实现 #####

/*
    // 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> preorder(Node root) {
        
            List<Integer> ans = new ArrayList<>();
            dfs(root, ans);
            return ans;
        }
    
        private void dfs(Node node, List<Integer> ans){
        
            if(node == null){
        
                return;
            }
            ans.add(node.val);
            List<Node> childrens = node.children;
            if(childrens != null){
        
                for(Node children : childrens){
        
                    dfs(children, ans);
                }
            }
        }
    }

##### Go 代码实现 #####

/**
     * Definition for a Node.
     * type Node struct {
     *     Val int
     *     Children []*Node
     * }
     */
    
    func preorder(root *Node) (ans[]int) {
        
        var dfs func(node *Node)
        dfs = func(node *Node) {
        
            if node == nil {
        
                return
            }
            ans = append(ans, node.Val)
            childrens := node.Children
            if childrens != nil {
        
                for _, children := range childrens {
        
                    dfs(children)
                }
            }
        }
        dfs(root)
        return
    }

##### 复杂度分析 #####

**时间复杂度：**  O ( N ) O(N) O(N)，`N` 为节点个数，每个节点都需要访问一次。

**空间复杂度：**  O ( N ) O(N) O(N)，`N` 为节点个数，空间复杂度取决于调用栈的深度，最大为 `N`。

--------------------

### 迭代解法 ###

创建一个辅助栈，因为是前序，前面的节点先遍历，所以我们可以让当前节点的子节点从后往前倒着入栈，这样出栈的时候就刚好是前序。

另外，每个出栈的节点，出栈时候将其 `value` 值加入答案，然后再将其下一级节点倒序入栈。

具体实现见代码，相信你看一眼就能明白。这种解法同样适用于二叉树的前序遍历。

##### Java 代码实现 #####

/*
    // 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> preorder(Node root) {
        
            List<Integer> ans = new ArrayList<>();
            if(root == null){
        
                return ans;
            }
            Deque<Node> stack = new LinkedList<>();
            stack.push(root);
    
            while(!stack.isEmpty()){
        
                Node top = stack.pop();
                ans.add(top.val);
                if(top.children != null){
        
                    for(int i = top.children.size() - 1; i >= 0; i--){
        
                        stack.push(top.children.get(i));
                    }
                }
            }
            return ans;
        }
    
    
    }

##### Go 代码实现 #####

/**
     * Definition for a Node.
     * type Node struct {
     *     Val int
     *     Children []*Node
     * }
     */
    
    func preorder(root *Node) (ans[]int) {
        
        if root == nil {
        
            return
        }
        stack := []*Node{
        root}
        for len(stack) > 0 {
        
            top := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            ans = append(ans, top.Val)
            if top.Children != nil {
        
                for i := len(top.Children) - 1; i >= 0; i--  {
        
                    stack = append(stack, top.Children[i])
                }
            }
            
        }
        return
    }

##### 复杂度分析 #####

**时间复杂度：**  O ( N ) O(N) O(N)，`N` 为节点个数，每个节点都需要访问一次。

**空间复杂度：**  O ( N ) O(N) O(N)，`N` 为节点个数，空间复杂度取决于调用栈的深度，最大为 `N`。

### 总结 ###

本题的解题思路可以当作模版记下来，`N` 可以换成任意数字，包括前面解过的二叉树。

[4817762f45a7a63d2682b1851b35560c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/861eab52c16f436b8f2e2ab0da7ada51.png
[badb3af3fcaedd038d6f1bb4e7ad95fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c30472f7a6824a1790a8be9e3c5cbe24.png