Day20- 二叉树part09

一、修剪二叉搜索树

题目一：669. 修剪二叉搜索树

669. 修剪二叉搜索树

给你二叉搜索树的根节点?root?，同时给定最小边界low?和最大边界?high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树?不应该?改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在?唯一的答案?。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

递归地检查每个节点，并决定是否保留它。

如果节点的值不在 low 和 high 的范围内，需要将其从树中移除。

如果节点的值小于 low，则它的左子树上所有节点的值也一定小于 low，因此可以丢弃整个左子树，并递归地在右子树上应用同样的过程。

同理，如果节点的值大于 high，则可以丢弃整个右子树，并递归地在左子树上进行修剪。

/*
 * @lc app=leetcode.cn id=669 lang=cpp
 *
 * [669] 修剪二叉搜索树
 */

// @lc code=start
/**
 * 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) {

        if (!root) return NULL;

        if (root->val < low) return trimBST(root->right, low, high);

        if (root->val > high) return trimBST(root->left, low, high);

        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        return root;
    }
};
// @lc code=end

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

题目一：108. 将有序数组转换为二叉搜索树

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

给你一个整数数组?nums?，其中元素已经按?升序?排列，请你将其转换为一棵?高度平衡?二叉搜索树。

高度平衡?二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

函数 sortedArrayToBST 接受一个数组和两个指标，表示当前处理的数组的部分。它选择数组中间的元素作为根节点，并递归地对左半部分和右半部分执行同样的操作，以创建左右子树

/*
 * @lc app=leetcode.cn id=108 lang=cpp
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * 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, int start, int end) {
        if (start > end) return NULL;

        int mid = start + (end - start) / 2;
        TreeNode* node = new TreeNode(nums[mid]);

        node->left = sortedArrayToBST(nums, start, mid - 1);
        node->right = sortedArrayToBST(nums, mid + 1, end);

        return node;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size() - 1);
    }
};
// @lc code=end

?三、把二叉搜索树转换为累加树

题目一：538. 把二叉搜索树转换为累加树

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

给出二叉?搜索?树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点?node?的新值等于原树中大于或等于?node.val?的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键?小于?节点键的节点。
• 节点的右子树仅包含键?大于?节点键的节点。
• 左右子树也必须是二叉搜索树。

?convertBSTUtil 函数执行反向中序遍历，并在遍历过程中累加并更新节点的值

/*
 * @lc app=leetcode.cn id=538 lang=cpp
 *
 * [538] 把二叉搜索树转换为累加树
 */

// @lc code=start
/**
 * 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:
    void convertBSTUtil(TreeNode* node, int& sum) {
        if (!node) return;
        convertBSTUtil(node->right, sum);
        sum += node->val;
        node->val = sum;
        convertBSTUtil(node->left, sum);
    }

    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        convertBSTUtil(root, sum);
        return root;
    }
};
// @lc code=end