算法记录第21天 [二叉树]

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

题目描述：

• 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
• 提醒一下，二叉搜索树满足下列约束条件：
  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。
• 示例 1：
  

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/description/

解题步骤 ：

1. 递归的遍历顺序：

   • tracseral 函数是一个递归的中序遍历（逆序）。在这个遍历中，先遍历右子树，再处理当前节点，最后遍历左子树。

2. 更新节点值：

   • root->val += pre; 将当前节点的值加上 pre（之前累积的节点值），然后更新 pre 为当前节点的新值。

3. 返回根节点：

   • 最后，convertBST 函数返回转换后的根节点，树已经被修改成累加树。

代码：

	int pre=0;
    void tracseral(TreeNode* root){
        // 退出条件
        if(root==nullptr) return ;
        // 右
        tracseral(root->right);
        // 中
        root->val += pre;
        pre = root->val;
        // 左
        tracseral(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
       tracseral(root);
       return root;
    }

2.LeetCode 669. 修剪二叉搜索树

题目描述：

• 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
• 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
• 示例 1：
  
  输入：root = [1,0,2], low = 1, high = 2
  输出：[1,null,2]

题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/description/

解题步骤 ：

1. 递归终止条件：

   • 如果当前节点为空 (root == nullptr)，则返回 nullptr，这是递归的终止条件。

2. 小于 low 的节点：

   • 如果当前节点的值小于 low，那么这个节点和它的左子树都不符合要求。可以直接递归修剪右子树，然后返回右子树的修剪结果。

3. 大于 high 的节点：

   • 如果当前节点的值大于 high，那么这个节点和它的右子树都不符合要求。可以直接递归修剪左子树，然后返回左子树的修剪结果。

4. 节点在合法区间内：

   • 如果当前节点的值在 [low, high] 范围内，那么这个节点是有效的，需要继续递归修剪它的左右子树，并返回该节点。

代码：

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        // 退出条件
        if(root==nullptr) return root;
        // 小于low
        if(root->val<low){
            TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if(root->val>high){
            TreeNode* left = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return left;
        }
        root->left = trimBST(root->left,low,high);
        root->right = trimBST(root->right,low,high);
        return root;
    }
  

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

题目描述：

• 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
• 示例 1：
  
  输入：nums = [-10,-3,0,5,9]
  输出：[0,-3,9,-10,null,5]
  解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
  

题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

解题步骤 ：

1. traversal 函数：

   • traversal 是一个递归函数，它接受一个数组 nums 和当前的左右边界 left 和 right。
   • 基本思路是：对于当前的子数组，选取中间元素作为根节点，然后递归构建左右子树。

2. 递归终止条件：

   • 当 left > right 时，说明当前子数组为空，没有元素可以构建树，这时返回 nullptr。

3. 选择中间元素：

   • int mid = (right - left) / 2 + left; 选择当前子数组的中间元素作为根节点。
   • 由于选择中间元素，保证了树是平衡的，避免了偏向一侧的情况。

4. 递归构建左右子树：

   • 对于当前的根节点（nums[mid]），递归地构建其左子树和右子树。
   • 左子树由 nums[left..mid-1] 构成，右子树由 nums[mid+1..right] 构成。

5. 返回根节点：

   • 最终递归的返回值是树的根节点。

代码：

  TreeNode* traversal(vector<int>& nums,int left,int right){
        // 退出条件
        if(left>right) return nullptr;
        int mid = (right-left)/2 +left;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums,left,mid-1);
        root->right = traversal(nums,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }