修剪二叉搜索樹

題目鏈接：669. 修剪二叉搜索樹

解題邏輯：

因為在刪除的同時要保證相對結構，所以我們不能沿用上一篇文章中的刪除邏輯，新的刪除邏輯為：

• 如果是葉子節點且不在范圍內，直接刪除
• 如果該節點值小于最小值，則返回該節點的右子樹（因為右子樹大于最小值，此時右子樹中不符合條件的值已經被刪除了）
• 如果該節點值大于最大值，則返回該節點的左子樹（因為左子樹小于最大值，此時左子樹中不符合條件的值已經被刪除了）

代碼如下：

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return null;TreeNode left = trimBST(root.left,low,high);TreeNode right = trimBST(root.right,low,high);if(root.val < low || root.val > high) {if(left == null && right == null) return null;else if(root.val < low) return right;else if(root.val > high) return left;}root.left = left;root.right = right;return root;}
}

將有序數組轉換為二叉搜索樹

題目鏈接：108. 將有序數組轉換為二叉搜索樹

本題是根據一個有序數組創建一個平衡的二叉搜索樹，核心思想就是：將數組從nums.length / 2開始切分，nums.length / 2索引對應的數值作為當前節點的值，左邊的為左子樹的節點值、右邊為右子樹的節點值。這樣遞歸切分構造，最后得到的一定是一個平衡的二叉搜索樹。

代碼如下：

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length == 0) return null;int devide = nums.length / 2;TreeNode left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, devide));TreeNode right;if(devide + 1 >= nums.length) right = sortedArrayToBST(new int[0]);else right = sortedArrayToBST(Arrays.copyOfRange(nums, devide + 1, nums.length));TreeNode node = new TreeNode(nums[devide]);node.left = left;node.right = right;return node;}
}

把二叉搜索樹轉換為累加樹

題目鏈接：538. 把二叉搜索樹轉換為累加樹

解題邏輯：

我們直接使用中序遍歷是從小到大遍歷，此時數值不好做累加（因為后面的值我們都不知道）。所以我們可以將整個二叉搜索樹進行翻轉，然后再使用中序遍歷修改節點，此時是從大到小遍歷，累加值是已知的，所以節點的值更好累加。構造完之后，再翻轉一次還原即可。

代碼如下：

class Solution {int num = 0;public TreeNode convertBST(TreeNode root) {reverseBST(root);changeBST(root);reverseBST(root);return root;}public void changeBST(TreeNode root){if(root == null) return;changeBST(root.left);int history = root.val;root.val += num;num += history;changeBST(root.right);}public void reverseBST(TreeNode root){if(root == null) return;reverseBST(root.left);reverseBST(root.right);TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}