Day20- 二叉树part09

发布时间:2024年01月05日

一、修剪二叉搜索树

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

669. 修剪二叉搜索树

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

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

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

如果节点的值不在 lowhigh 的范围内,需要将其从树中移除。

如果节点的值小于 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

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