🔥博客主页： 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<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root){
return res;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int currentSize = q.size();
res.push_back(vector<int> ());
for(int i = 0; i < currentSize; ++i){
auto node = q.front();
q.pop();
res.back().push_back(node -> 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<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) {return res;}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int currentsize = q.size();
res.push_back(vector<int>());
for(int i = 0; i < currentsize; i++){
auto* node = q.front();
q.pop();
res.back().push_back(node -> 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<int> &res){
if(!root){
return;
}
res.push_back(root -> val);
for(auto &z : root -> children){
qianxu(z,res);
}
}
vector<int> preorder(Node* root) {
vector<int> 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<int> &res){
if(!root){
return;
}
res.push_back(root -> val);
for(auto &z : root -> children){
qianxu(z,res);
}
}
vector<int> preorder(Node* root) {
vector<int> 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 < low){
return rangeSumBST(root -> right,low,high);
}
if(root -> val > high){
return rangeSumBST(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<int>& 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∣ 次操作，将较小的值增加至与较大的值相等。待考虑完所有叶节点之后，互为兄弟节点的叶节点的值两两相等（并且根到它们的路径值显然也相等）。如果我们还需要操作某个叶节点，那么为了使得路径值相等，它的兄弟节点同样也需要操作。此时就需要两次操作，但不如直接操作它们的双亲节点，可以省去一次操作。
因此，所有的叶节点都无需进行操作。我们就可以将它们全部移除。为了使得路径值保持不变，我们可以将叶节点的值增加至它们的双亲节点。这样一来，所有的双亲节点都变成了新的叶节点，我们重复进行上述操作即可。当只剩一个节点（根节点）时，就可以得到最终的答案。
