刷題小記：
上期學習了二叉搜索樹的插入和刪除操作，這次學習如何按區間修剪二叉搜索樹。還有兩題，關于借助二叉搜索樹的有序特性進行轉換。
669.修剪二叉搜索樹（669.修剪二叉搜索樹）
題目分析：
給定一個二叉搜索樹的根節點root，以及最小邊界low和最大邊界high，通過修建二叉搜索樹，使得所有節點的值在[low, high]之中。并保證不改變保留在樹中元素的相對結構。
解題思路：
在450.刪除二叉搜索樹中的節點一題中，我們已經研究了二叉搜索樹節點的刪除方式，在此題之中，我們同樣也面臨節點刪除的情況，結合情景進一步分析如下：
- 小于下邊界的節點，其左子樹必然全部出界，均需剪枝；
- 大于上邊界的節點，其右子樹必然全部出界，均需剪枝。
只需反復運用這兩條法制，并遍歷整棵樹，能夠確保結果正確。
解題步驟：
考慮使用前序遍歷的遞歸解決：
- 遞歸的參數：當前節點，下界，上界
- 遞歸的返回值：修剪后的當前節點所在子樹的根節點
- 遞歸的終止條件：遇到空節點，返回null
- 遞歸的單層遞歸邏輯：
-
- 對于當前節點cur，如果cur.val<low，那么遞歸cur的右子樹的修剪結果并直接返回
- 對于當前節點cur，如果cur.val>high，那么遞歸cur的左孩子的修剪結果并直接返回
- 遞歸修剪cur的左孩子
- 遞歸修剪cur的右孩子
- 返回修剪完畢的cur
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) 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;}
}108.將有序數組轉換為二叉搜索樹（108.將有序數組轉換為二叉搜索樹）
題目分析：
給定一個升序排列的整數數組nums，需將其轉換成一棵平衡二叉搜索樹（左右子樹相差高度不超過1）。
解題重點：
構造方式：
觀察題目示例發現，構造方式存在左傾式和右傾式兩種。
左傾式：以大者為父節點，小者為左孩子節點。
右傾式：以小者為父節點，大者為右孩子節點。
此處我默認選擇左傾式進行構造。
轉換方式：
觀察完構造方式，再來觀察如何進行轉換。
給定nums數組（包括過程中的子數組），要么長度為奇，要么為偶。
- 若為奇數組，則中間值為當前子樹的根節點，以中間值（下標為n/2）為界的左子數組轉換成左子樹，右子數組轉換成右子樹
- 若為偶數組，由于先前采用了左傾式的構造方式（與奇數組情況統一），此處選擇以下標為n/2處為中間值（數組長為n），則中間值為當前子樹的根節點，以中間值為界的左子數組轉換成左子樹，右子數組轉換成右子樹
解題步驟：
構造前序遍歷的遞歸函數traversal如下：
- 遞歸的參數：轉換數組nums，左邊界下標left，右邊界下標right（左閉右閉）
- 遞歸的返回值：轉換后所得子樹的根節點root
- 遞歸的終止條件：left > right時，返回空節點null
- 遞歸的單層遞歸邏輯：
-
- 取mid = (right + left + 1) / 2，用下標為mid的值構造當前子樹的根節點root
- 用new_left = left，new_right = mid - 1的區間構造左子樹
- 用new_left = mid + 1，new_right = rigt的區間構造右子樹
- 最終返回root。
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums, 0, nums.length - 1);}public TreeNode traversal(int[] nums, int left, int right) {if (left > right) return null;int mid = (right + left + 1) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = traversal(nums, left, mid - 1);root.right = traversal(nums, mid + 1, right);return root;}
}538.把二叉搜索樹轉換為累加樹（538.把二叉搜索樹轉換為累加樹）
題目分析：
給出一棵二叉搜索樹的根節點root，該樹的節點值均不相同，現要求將其轉換成累加樹——每個節點值的新值等于原樹中大于等于原值的值之和。
解題思路：
大于等于原值的值，除自身的值相等外，無其他相等的值；而大于原值的其他值，出現在該值的“右側”，根據二叉搜索樹的特性，這個“右側”描述為：該節點的最左祖先節點x，其父節點x_dad和x_dad的右子樹的全部節點。
可知，欲將二叉搜索樹轉換成這種累加樹，應當從原樹的右下方開始運算，即右中左的順序，即倒序的中序遍歷，在該遍歷順序下，每一個中節點的值更改為原節點值+前綴節點值。
解題步驟：
采用右中左的遍歷順序，構造遞歸函數：
- 遞歸的參數：當前節點root
- 遞歸的返回值：更改后的節點
- 遞歸的終止條件：遇到空節點，返回null
- 遞歸的單層遞歸邏輯：
-
- 向右遞歸，更新累加后的“右節點”
- 若前綴節點pre不為空，則更新當前節點值累加上前綴節點pre的值，并更新前綴節點pre
- 向左遞歸，更新累加后的“左節點”
- 返回root
class Solution {TreeNode pre = null;public TreeNode convertBST(TreeNode root) {if (root == null) return root;root.right = convertBST(root.right);if (pre != null) root.val += pre.val;pre = root;root.left = convertBST(root.left);return root;}
}
