day 23二叉树（九）

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;
    }
};