代碼隨想錄打卡第23天 669. 修剪二叉搜索樹 108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹 538. 把二叉搜索樹轉(zhuǎn)換為累加樹
669. 修剪二叉搜索樹
題目鏈接：https://leetcode.cn/problems/trim-a-binary-search-tree/
算法思想：
? ? 二叉樹的終止條件：
? ? ? ? 遇到比low小或者比high大的元素逊彭，開始處理先誉。
? ? ? ? 如果遇到比low小的元素，那就遞歸處理它的右孩子，并且用left接住這個遞歸返回的節(jié)點，返回給上一層谴餐。
? ? ? ? 如果遇到比high大的元素，那就遞歸處理它的左孩子，并且用right接住這個遞歸返回的節(jié)點橘洞，返回給上一層。
代碼：
class Solution {
public:
? ? TreeNode* trimBST(TreeNode* root, int low, int high) {
? ? ? ? //
? ? ? ? if(root==NULL)
? ? ? ? ? ? return root;
? ? ? ? if(root->val < low)
? ? ? ? {
? ? ? ? ? ? //找到比low小的根節(jié)點了,去看下右孩子需要保留的地方
? ? ? ? ? ? TreeNode* left = trimBST(root->right, low, high);
? ? ? ? ? ? return left;
? ? ? ? }
? ? ? ? if(root->val > high)
? ? ? ? {
? ? ? ? ? ? TreeNode* right = trimBST(root->left, low, high);
? ? ? ? ? ? return right;
? ? ? ? }
? ? ? ? root->left = trimBST(root->left, low, high);
? ? ? ? root->right = trimBST(root->right, low, high);
? ? ? ? return root;
? ? }
};
108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
題目鏈接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
算法思想：相當于是進行二分查找说搅，均勻的把數(shù)組分成平衡的兩個部分炸枣，遞歸構(gòu)造左右孩子。
注意區(qū)間的定義是左閉右開還是左閉右閉弄唧。
代碼：
class Solution {
public:
? ? TreeNode* buildtree(vector<int>& nums, int start, int end)
? ? {
? ? ? ? if(start>=end)
? ? ? ? ? ? return NULL;
? ? ? ? int mid = (start+end)/2;
? ? ? ? TreeNode* root = new TreeNode(nums[mid]);
? ? ? ? root->left = buildtree(nums, start, mid);
? ? ? ? root->right = buildtree(nums, mid+1, end);
? ? ? ? return root;
? ? }
? ? TreeNode* sortedArrayToBST(vector<int>& nums) {
? ? ? ? //可以采用二分法對樹進行構(gòu)建
? ? ? ? TreeNode* root = buildtree(nums, 0, nums.size());
? ? ? ? return root;
? ? }
};
538. 把二叉搜索樹轉(zhuǎn)換為累加樹
題目鏈接：https://leetcode.cn/problems/convert-bst-to-greater-tree/
算法思想：
? ? 可以想到适肠，用二叉搜索樹中序遍歷是將從小到大遍歷。我們現(xiàn)在需要從大到小遍歷候引，就采用右中左的方式遍歷侯养，并用一個全局變量sum記錄累加的數(shù)值進行更新。
代碼：
class Solution {
public:
? ? int sum=0;
? ? void countval(TreeNode* root)
? ? {
? ? ? ? if(root==NULL)
? ? ? ? ? ? return;
? ? ? ? countval(root->right);
? ? ? ? sum = sum+root->val;
? ? ? ? root->val = sum;
? ? ? ? countval(root->left);
? ? }
? ? TreeNode* convertBST(TreeNode* root) {
? ? ? ? countval(root);
? ? ? ? return root;
? ? }
};
