---

一、修剪二叉搜索樹-LeetCode 669

Leecode鏈接: leetcode 669
文章鏈接: 代碼隨想錄
視頻鏈接: B站

給你二叉搜索樹的根節點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節點的值在[low, high]中。修剪樹 不應該 改變保留在樹中的元素的相對結構 (即，如果沒有被移除，原有的父代子代關系都應當保留)。 可以證明，存在 唯一的答案 。

示例：

輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]

思路

這道題我跟視頻鏈接的思路稍微有點不一樣，我用的是后序遍歷。優先判斷左右子樹的狀態，如果左右子樹都為空，那么該節點就是葉子節點，根據自身值是否滿足區間要求返回空或者本身即可。如果不是葉子節點，那么需要對右子樹著重判斷，因為如果該節點值不滿足[low,high]區間，不代表該節點的右子樹值不滿足這個區間，如果滿足就返回右子樹的節點，否則返回空。

實現代碼

個人代碼

//cpp
class Solution {
public:TreeNode* test(TreeNode* root,int low,int high){if(root == nullptr)return root;root->left = test(root->left,low,high);root->right = test(root->right,low,high);if(root->val<low || root->val>high){//不滿足區間條件，根據左右子樹情況返回不同值if(root->left)return root->left;if(root->right)return root->right;if(root->right == nullptr) return nullptr;}return root;//滿足區間條件返回本身}TreeNode* trimBST(TreeNode* root, int low, int high) {return test(root,low,high);}
};

視頻鏈接代碼

//cpp
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); // 尋找符合區間[low, high]的節點return right;}if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 尋找符合區間[low, high]的節點return left;}root->left = trimBST(root->left, low, high); // root->left接入符合條件的左孩子root->right = trimBST(root->right, low, high); // root->right接入符合條件的右孩子return root;}
};

個人問題

沒有明顯問題，除了花的時間有點久。

---

二、將有序數組轉化為二叉搜索樹-LeetCode 108

Leecode鏈接: LeetCode 108
文章鏈接: 代碼隨想錄
視頻鏈接: B站

給你一個整數數組 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵
平衡二叉搜索樹。

示例：

輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：

思路

數組是有序的，每次取數組中間值，然后將數組切割，左區間左子樹遞歸處理，右區間右子樹遞歸處理。

實現代碼

//cpp
class Solution {
public:TreeNode* build(vector<int>& nums,int left,int right){if(left>right){return nullptr;}int mid = (right - left)/2 + left;TreeNode* node = new TreeNode(nums[mid]);//取中間值作為父節點node->left = build(nums,left,mid - 1);node->right = build(nums,mid + 1,right);return node;}TreeNode* sortedArrayToBST(vector<int>& nums) {return build(nums,0,nums.size() - 1);}
};

個人問題

簡單題，無明顯問題。

---

三.把二叉樹搜索轉化為累加樹-LeeCode 538

Leecode鏈接: LeetCode 538
文章鏈接: 代碼隨想錄
視頻鏈接: B站

給出二叉 搜索 樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和。

示例：

輸入：[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]

思路

題目其實大意應該是使用右中左遍歷的順序來對節點值重新賦值，使用一個全局變量來保存累加和，然后遞歸處理每個節點即可，理清這個意思題目就基本知道怎么寫了。

實現代碼

//cpp
class Solution {
public:int sum = 0;void test(TreeNode* root){if(root == nullptr){return;}test(root->right);//右子樹sum = root->val + sum;//更新sum值root->val = sum;//重新賦值test(root->left);//左子樹return;}TreeNode* convertBST(TreeNode* root) {test(root);return root;}
};

個人問題

簡單題，無明顯問題。