【每日一题】 2024年2月汇编（下）

博客主页：A_SHOWY
系列专栏：力扣刷题总结录数据结构云计算数字图像处理力扣每日一题_

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

103. 二叉树的锯齿形层序遍历https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

和前面的题目还是一样的，核心还是BFS，就是res结果对于偶数个数的元素，内部数组进行一个reverse交换。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:vector<vector> zigzagLevelOrder(TreeNode* root) {vector<vector> res;if(!root){return res;}queue q;q.push(root);while(!q.empty()){ int currentSize = q.size(); res.push_back(vector ()); for(int i = 0; i  val);if(node -> left) q.push(node -> left);if(node -> right) q.push(node -> right); }}for(int i = 0; i < res.size(); i++){if(i % 2){int start = 0;int end = res[i].size() - 1;while(start <= end){swap(res[i][start],res[i][end]);start++;end --;}}}return res;}};

【2.17】429.N叉树的层序遍历

429. N 叉树的层序遍历https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

这个月和树干上了，每天都是DFS和BFS，这里的话继续用BFS思路可以说完全一样，N叉树的话其实就是多一个循环，以前的把左右节点加入q，现在是把所有子节点children加进去

参考上旬的二叉树的层序遍历

class Solution {public:vector<vector> levelOrder(TreeNode* root) {vector<vector> res;if(!root) {return res;}queueq;q.push(root);while(!q.empty()){int currentsize = q.size();res.push_back(vector());for(int i = 0; i  val);if(node -> left) q.push(node -> left);if(node -> right) q.push(node -> right);}}return res;}};

【2.18】589.N叉树的前序遍历

589. N 叉树的前序遍历https://leetcode.cn/problems/n-ary-tree-preorder-traversal/

同前些日子做的二叉树前序没区别，就是一个DFS的递归就能解决

class Solution {public:void qianxu(Node* root,vector &res){if(!root){return;} res.push_back(root -> val);for(auto &z : root -> children){ qianxu(z,res);}}vector preorder(Node* root) {vector res;qianxu(root,res);return res;}};

【2.19】590.N叉树的后序遍历

590. N 叉树的后序遍历https://leetcode.cn/problems/n-ary-tree-postorder-traversal/

DFS递归的一个N叉后序遍历和前序一样

class Solution {public:void qianxu(Node* root,vector &res){if(!root){return;} res.push_back(root -> val);for(auto &z : root -> children){ qianxu(z,res);}}vector preorder(Node* root) {vector res;qianxu(root,res);return res;}};

【2.26】938.二叉搜索树的范围和

938. 二叉搜索树的范围和https://leetcode.cn/problems/range-sum-of-bst/

二叉搜索树需要知道的性质是，对于每一个节点，其左子树一定比节点小，右子树的值一定比该节点大，其实就是一个中序遍历的DFS。

class Solution {public:int rangeSumBST(TreeNode* root, int low, int high) { if(root == nullptr){ return 0; } int sum = 0; if(root -> val  right,low,high); } if(root -> val > high){ returnrangeSumBST(root -> left,low,high); } sum += root -> val + rangeSumBST(root -> left,low,high) + rangeSumBST(root -> right,low,high); return sum; }};

【2.28】2673.使二叉树所有路径的值相等的最小代价

2673. 使二叉树所有路径值相等的最小代价https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/

逆序遍历，整体思路非常巧妙

class Solution {public:int minIncrements(int n, vector& cost) {int ans = 0;for(int i = n - 2; i > 0; i -= 2){ ans += abs(cost[i] - cost[i + 1]); cost[i/2] += max(cost[i],cost[i + 1]);}return ans;}};

对于任一叶结点，它的值为 x，它的兄弟节点的值为 y。可以发现，对于树上的其余节点，它们要么同时是这两个叶节点的祖先，要么同时不是这两个叶节点的祖先。对这些节点进行一次操作，要么同时增加了根到这两个叶节点的路径值 1，要么没有任何效果。因此，要想使得根到这两个叶节点的路径值相等，我们只能增加 x 和 y本身。由于我们希望操作次数最少，那么应该进行∣x−y∣ 次操作，将较小的值增加至与较大的值相等。待考虑完所有叶节点之后，互为兄弟节点的叶节点的值两两相等（并且根到它们的路径值显然也相等）。如果我们还需要操作某个叶节点，那么为了使得路径值相等，它的兄弟节点同样也需要操作。此时就需要两次操作，但不如直接操作它们的双亲节点，可以省去一次操作。

因此，所有的叶节点都无需进行操作。我们就可以将它们全部移除。为了使得路径值保持不变，我们可以将叶节点的值增加至它们的双亲节点。这样一来，所有的双亲节点都变成了新的叶节点，我们重复进行上述操作即可。当只剩一个节点（根节点）时，就可以得到最终的答案。