day 23二叉树(九)

发布时间:2023年12月21日

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;
    }
};
文章来源:https://blog.csdn.net/qq_56913257/article/details/135127501
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。