669. 修剪二叉搜索树

解题思路

在上一题的删除二叉树节点中,我们通过在这一层的返回值,让上一层接住,也就是上一层对应的孩子接住这层的返回值,达到删除节点的目的(C++要手动清理内存)。在这题有一些注意事项如下:我们需要判断,如果当前删除节点的值小于左边界,但要去右遍历,是可能符合区间的,同样的大于右边界,要去左遍历

 代码随想录算法训练营第二十五天 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树-LMLPHP

 

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
             if(root == nullptr) return nullptr;
             if(root->val < low)//当前节点小于左边界,要去判断一下他的右子树
             {
                  TreeNode*  right = trimBST(root->right,low,high);  //对右子树修剪
                  return right;
             }
             if(root->val > high)
             {
                 TreeNode* left = trimBST(root->left,low,high);   //对左子树修剪
                 return left;
             }
             root->left  = trimBST(root->left,low,high);
             root->right = trimBST(root->right,low,high);
             return root;
    }
};

108.将有序数组转换为二叉搜索树

解题思路

这里强调平衡是因为一个数组可以构成一个链式的二叉树,因此强调平衡

代码随想录算法训练营第二十五天 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树-LMLPHP 

整体的思路就是找到一个中间节点,分为左右区间,去构造左区间和右区间

class Solution {
public:
    TreeNode* travelSal(vector<int>& nums, int left, int right)
    {
          //左闭右闭区间
          if(left>right) return nullptr;
          int mid = left + ((right-left) >>1) ;  //这是向下取整,取左侧的元素
          TreeNode* root = new TreeNode(nums[mid]);
          root->left = travelSal(nums,left,mid-1);
          root->right = travelSal(nums,mid+1,right);
          return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
            return travelSal(nums,0,nums.size()-1);
    }
};

538.把二叉搜索树转换为累加树

 解题思路

我们利用双指针,再利用右中左的遍历顺序相加即可

class Solution {
private:
int pre = 0;
public:
    void SumTree(TreeNode* node)
    {
        if(node == nullptr) return;
        SumTree(node->right);    //右子树
        //中节点
             node->val = pre + node->val;
             pre = node->val;
        SumTree(node->left);   //左子树
    }

    TreeNode* convertBST(TreeNode* root) {
          SumTree(root);
          return root;
    }
};

二叉树总结(代码随想录)

代码随想录

收获

二叉树终于结束啦,准备回溯! 

05-12 05:15