LeetCode 每日一题 树合集 Day 16 - 27

���于是开学了，想了想每日一更频率太高，以后每周更新一周的每日一题。

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

树中节点数目在范围 [0, 2000] 内

-100 public: vector if (!root) { return {}; } vector tt.clear(); temp.clear(); for (auto it : lists) { tt.push_back(it-val); if (it-left) { temp.push_back(it->left); } if (it->right) { temp.push_back(it->right); } } lists = temp; if (!isLeft) { reverse(tt.begin(), tt.end()); } isLeft = !isLeft; res.push_back(tt); } return res; }};

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

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

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

示例 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,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000

树的节点总数在 [0, 10^4] 之间

树的层序遍历，代码随想录的卡哥总结的很好，读者有兴趣可以看看：「代码随想录」二叉树层序遍历登场：我要打十个！

/*// Definition for a Node.class Node {public:    int val;    vector children;    Node() {}    Node(int _val) {        val = _val;    }    Node(int _val, vector _children) {        val = _val;        children = _children;    }};*/class Solution {public:    vector levelOrder(Node* root) {        queue que;        vector result;        if (root != NULL)            que.push(root);        while (!que.empty()) {            int size = que.size();            vector vec;            for (int i = 0; i val);                for (int i = 0; i children.size(); i++) {                    if (node->children[i]) {                        que.push(node->children[i]);                    }                }            }            result.push_back(vec);        }        return result;    }};

589. N 叉树的前序遍历

给定一个 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, 104]内

0 private: vector if (root == NULL) { return; } res.push_back(root-val); for (int i = 0; i children[i]); } }public: vector preorder(Node* root) { res.clear(); traversal(root); return res; }};

590. N 叉树的后序遍历

/*// Definition for a Node.class Node {public:    int val;    vector children;    Node() {}    Node(int _val) {        val = _val;    }    Node(int _val, vector _children) {        val = _val;        children = _children;    }};*/class Solution {private:    vector res;    void traversal(Node* root) {        if (root == NULL) {            return;        }        for (int i = 0; i children.size(); i++) {            traversal(root->children[i]);        }        res.push_back(root->val);    }public:    vector postorder(Node* root) {        res.clear();        traversal(root);        return res;    }};

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]

输出: [-1]

提示:

1 private: vector if (left right) return nullptr; TreeNode* node = new TreeNode(preorder[root]); int i = dic[preorder[root]]; node-left = recur(root + 1, left, i - 1); node-right = recur(root + i - left + 1, i + 1, right); return node; }public: TreeNode* buildTree(vector this-preorder = preorder; for (int i = 0; i

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]

输出：[-1]

提示:

1 public: unordered_map int n = inorder.size(); for (int i = 0; i

2867. 统计树中的合法路径数目(Hard)

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。

路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

示例 1：

输入：n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]

输出：4

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

  只有 4 条合法路径。

  示例 2：

  输入：n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]

  输出：6

  解释：恰好有一个质数编号的节点路径有：

  • (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
  • (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
  • (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
  • (1, 6) 因为路径 1 到 6 只包含一个质数 3 。
  • (2, 4) 因为路径 2 到 4 只包含一个质数 2 。
  • (3, 6) 因为路径 3 到 6 只包含一个质数 3 。

    只有 6 条合法路径。

    提示：

    1 np[1] = true; for (int i = 2; i * i if (!np[i]) { for (int j = i * i; j np[j] = true; } } } return 0;}();class Solution {public: long long countPaths(int n, vector vector int x = e[0], y = e[1]; g[x].push_back(y); g[y].push_back(x); } vector nodes.push_back(x); for (int y : g[x]) { if (y != fa && np[y]) { dfs(y, x); } } }; long long ans = 0; for (int x = 1; x if (np[x]) continue; // 跳过非质数 int sum = 0; for (int y : g[x]) { // 质数 x 把这棵树分成了若干个连通块 if (!np[y]) continue; if (size[y] == 0) { // 尚未计算过 nodes.clear(); dfs(y, -1); // 遍历 y // 所在连通块，在不经过质数的前提下，统计有多少个非质数 for (int z : nodes) { size[z] = nodes.size(); } } // 这 size[y] 个非质数与之前遍历到的 sum // 个非质数，两两之间的路径只包含质数 x ans += (long long)size[y] * sum; sum += size[y]; } ans += sum; // 从 x 出发的路径 } return ans; }};public: long long countPaths(int n, vector vector adj[e[0]].emplace_back(e[1]); adj[e[1]].emplace_back(e[0]); } bool prime[n + 1]; memset(prime, true, sizeof(prime)); bool visited[n + 1]; memset(visited, false, sizeof(visited)); function for (int p = 2; p * p if (prime[p] == true) { for (int i = p * p; i if (prime[cur]) { for (int a : adj[cur]) { if (!visited[a]) { visited[a] = true; traverse(a); } } } else { if (group[cur] != 0) return; queue int l = bfs.size(); for (int i = 0; i