这是雷军的简历，落魄时卡里只有冰冷的40亿

猿大侠 · 公众号 · · 2024-04-13 23:58

正文

转自：数据结构与算法

最近在网上浏览信息时，偶然看到了雷军的两份简历，一份是详细的工作履历，另一份则是他的干部履历表。

雷军，毕业于武汉大学，毕业后，顺利进入了金山软件，开始了自己的职业生涯，但他并没有满足于在金山软件的成就，之后创建小米科技，将小米科技打造成了一家具有影响力的科技公司，这就是雷军大佬的真实人生。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第589：N 叉树的前序遍历。

问题描述

来源：LeetCode第589题

难度：简单

给定一个 n 叉树的根节点 root ，返回其节点值的前序遍历。n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例1：

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

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

示例2：

输入：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

问题分析

这题是让计算N叉树的前序遍历，我们参照二叉树的前序遍历来解这题。二叉树的前序遍历是先打印根节点，然后在分别遍历左子树和右子树。 N 叉树也是一样，先打印N叉树的根节点，然后再递归遍历N叉树的所有子节点，代码比较简单，我们来看下。

JAVA：

public List preorder(Node root) {
    List ans = new ArrayList<>();
    dfs(root, ans);
    return ans;
}

private void dfs(Node root, List ans) {
    if (root == null)
        return;
    ans.add(root.val);// 添加当前节点
    for (Node cur : root.children)// 递归所有子节点
        dfs(cur, ans);
}

C++：

public:
    vector<int> preorder(Node *root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }

    void dfs(Node *root, vector<int> &ans) {
        if (root == nullptr