day23
代码随想录
2023.12.21
1. 669修剪二叉搜索树
这道题,简直了,废了半天功夫,开始感觉没啥啊,跟昨天删除二叉树节点一样啊,不满足要求的,删掉就行呗,写了半天,一直报错,然后debug,太费时间了,结果最后发现,是主函数return写错了,服啦。
并且这道题比删除节点更简单,想一想,如果一个节点不不满足要求,那么,该节点的某一子树也一定不满足,所以直接返回另一子树的遍历结果就行,不用讨论各种情况。
/**
* 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:
TreeNode* trimBST(TreeNode* root, int low, int high) {
return travel(root, low, high);
}
TreeNode* travel(TreeNode*node, int low, int high){
if(node==NULL)
return NULL;
if (node->val < low) {
TreeNode* right = travel(node->right, low, high);
return right;
}
if (node->val > high) {
TreeNode* left = travel(node->left, low, high);
return left;
}
if(node->left) node->left=travel(node->left, low, high);
if(node->right) node->right=travel(node->right, low, high);
return node;
}
};
2. 108将有序数组转换为二叉搜索树
开始我在想,怎么保持一直平衡呢,有点没有头绪,以为定义一个整理二叉树的函数,每次构造完后,用该函数处理一下,但感觉有些麻烦,看了文字讲解,每次将有序数组从中间划分,保证平衡,瞬间悟了!
/**
* 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:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode*root = Build(nums,0,nums.size()-1);
return root;
}
TreeNode* Build(vector<int>& nums, int low, int high){
if(low>high)
return NULL;
int mid = low + (high-low)/2;
TreeNode*node = new TreeNode(nums[mid]);
node->left = Build(nums, low, mid-1);
node->right = Build(nums, mid+1, high);
return node;
}
};
3. 538把二叉搜索树转换为累加树
这题没接触过,有点懵,以为要新建一棵树,遍历在原树的所有节点,符合要求的,值累加就可以,但是逻辑理不清,写的太麻烦了。最后看文字讲解,恍然大悟,中序的反向遍历,这样遍历值就是从大到小了,累加就是数值往后加,比如第一个遍历的节点,也就是最大的,此时没有任何需要累加的,因此表示累加和的变量初始值为1,遍历节点后将该节点值加给该变量;之后第二个节点,满足要求的就是最有一个值,不就是我们定义的累加变量的值吗?所以依次往后变量即可。
/**
* 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:
int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur) { // 右中左遍历
if (cur == NULL) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
TreeNode* convertBST(TreeNode* root) {
int pre=0;
traversal(root);
return root;
}
};