代碼隨想錄–二叉樹部分

day 21 二叉樹第八天

---

---

一、力扣669–修建二叉搜索樹

代碼隨想錄題目鏈接：代碼隨想錄

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

這里不能想的太復雜，要注意是二叉搜索樹，如果某個節點比low還小，那說明它左子樹可以整個刪了，反之亦然

那么向下搜索，如果遇到小于low的節點，就遞歸它的右子樹，大于high就左子樹

至于刪除節點，只需要在return的時候注意一下不是return root，而是return遞歸結果

只不過這樣沒法釋放內存，會有些浪費

代碼如下：

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(!root) return nullptr;if(root->val < low){TreeNode * right = trimBST(root->right, low, high);return right;}if(root->val > high){TreeNode * left = trimBST(root->left, low, high);return left;}root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}   
};

二、力扣108–將有序數組轉換為二叉搜索樹

代碼隨想錄題目鏈接：代碼隨想錄

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

核心思路就是遞歸構建，并且每次都對nums進行分割，分成左子樹數組和右子樹數組，和構建最大二叉樹一個想法

代碼如下：

class Solution {
public:TreeNode* traversal(vector<int>& nums, int left, int right){if (left > right) return nullptr;int mid = left + (right - left) / 2;TreeNode * curr = new TreeNode(nums[mid]);curr->left = traversal(nums, left, mid - 1);curr->right = traversal(nums, mid + 1, right);return curr;}TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode * root = traversal(nums, 0, nums.size() - 1);return root;}
};

三、力扣538–把二叉搜索樹轉換為累加樹

代碼隨想錄題目鏈接：代碼隨想錄

給出二叉 搜索 樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和。
提醒一下，二叉搜索樹滿足下列約束條件：
節點的左子樹僅包含鍵 小于 節點鍵的節點。
節點的右子樹僅包含鍵 大于 節點鍵的節點。
左右子樹也必須是二叉搜索樹。

簡單講就是把每個大于當前節點的值都加起來，和當前節點相加作為該節點的新值

那么只要從右葉子節點向左邊遍歷，每遍歷一次就對sum累加一次，加到最后就結束了

這里sum定義成全局變量，記錄遍歷以來每個node的值之和

也就是反過來的中序遞歸

代碼如下：

class Solution {
public:int sum = 0;void traversal(TreeNode * curr){if(!curr) return;traversal(curr->right);curr->val += sum;sum = curr->val;traversal(curr->left);}TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};