LC 589. N 叉树的前序遍历

题目描述

这是 LeetCode 上的 589. N 叉树的前序遍历 ，难度为简单。

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

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

示例 1：

1
2
3

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

输出：[1,3,5,6,2,4]

示例 2：

1
2
3

输入：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, 10^4]$ 内
$0 <= Node.val <= 10^4$
$n$ 叉树的高度小于或等于 $1000$

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

递归

常规做法，不再赘述。

Java 代码：

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

C++ 代码：

class Solution {
public:
    vector<int> ans;
    vector<int> preorder(Node* root) {    
        dfs(root, ans);
        return ans;
    }
    void dfs(Node* root, vector<int>& ans) {
        if (!root) return;
        ans.push_back(root->val);
        for (Node* node : root->children) dfs(node, ans);
    }
};

Python 代码：

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node):
            if not node:
                return
            ans.append(node.val)
            for child in node.children:
                dfs(child)
        dfs(root)
        return ans

时间复杂度：$O(n)$
空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

迭代

针对本题，使用「栈」模拟递归过程。

迭代过程中记录 (node = 当前节点, cnt = 当前节点遍历过的子节点数量) 二元组，每次取出栈顶元素，如果当前节点是首次出队（当前遍历过的子节点数量为 $cnt = 0$），则将当前节点的值加入答案，然后更新当前元素遍历过的子节点数量，并重新入队，即将 $(node, cnt + 1)$ 入队，以及将下一子节点 $(node.children[cnt], 0)$ 进行首次入队。

Java 代码；

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{root, 0});
        while (!d.isEmpty()) {
            Object[] poll = d.pollLast();
            Node t = (Node)poll[0]; Integer cnt = (Integer)poll[1];
            if (t == null) continue;
            if (cnt == 0) ans.add(t.val);
            if (cnt < t.children.size()) {
                d.addLast(new Object[]{t, cnt + 1});
                d.addLast(new Object[]{t.children.get(cnt), 0});
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        stack<pair<Node*, int>> stk;
        stk.push({root, 0});
        while (!stk.empty()) {
            auto [node, cnt] = stk.top();
            stk.pop();
            if (!node) continue;
            if (cnt == 0) ans.push_back(node->val);
            if (cnt < node->children.size()) {
                stk.push({node, cnt + 1});
                stk.push({node->children[cnt], 0});
            }
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        stk = [(root, 0)]
        while stk:
            node, cnt = stk.pop()
            if not node:
                continue
            if cnt == 0:
                ans.append(node.val)
            if cnt < len(node.children):
                stk.append((node, cnt + 1))
                stk.append((node.children[cnt], 0))
        return ans

时间复杂度：$O(n)$
空间复杂度：$O(n)$

通用「递归」转「迭代」

另外一种「递归」转「迭代」的做法，是直接模拟系统执行「递归」的过程，这是一种更为通用的做法。

由于现代编译器已经做了很多关于递归的优化，现在这种技巧已经无须掌握。

在迭代过程中记录当前栈帧位置状态 loc，在每个状态流转节点做相应操作。

Java 代码：

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{0, root});
        while (!d.isEmpty()) {
            Object[] poll = d.pollLast();
            Integer loc = (Integer)poll[0]; Node t = (Node)poll[1];
            if (t == null) continue;
            if (loc == 0) {
                ans.add(t.val);
                d.addLast(new Object[]{1, t});
            } else if (loc == 1) {
                int n = t.children.size();
                for (int i = n - 1; i >= 0; i--) {
                    d.addLast(new Object[]{0, t.children.get(i)});
                }
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        stack<pair<int, Node*>> stk;
        stk.push({0, root});
        while (!stk.empty()) {
            auto [loc, node] = stk.top();
            stk.pop();
            if (!node) continue;
            if (loc == 0) {
                ans.push_back(node->val);
                stk.push({1, node});
            } else if (loc == 1) {
                for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {
                    stk.push({0, *it});
                }
            }
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        stack = [(0, root)]
        while stack:
            loc, node = stack.pop()
            if not node:
                continue
            if loc == 0:
                ans.append(node.val)
                stack.append((1, node))
            elif loc == 1:
                for child in reversed(node.children):
                    stack.append((0, child))
        return ans

时间复杂度：$O(n)$
空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.589 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

树的搜索递归迭代

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 2049. 统计最高分的节点数目上一篇

LC 798. 得分最高的最小轮调下一篇