---

前言

迭代法都沒看主要是669和538【538很簡單】

669. 修剪二叉搜索樹

思路

不用看教程，思路很清晰
💖總體思路【單層遞歸邏輯】

1. 如果當前節點的值小于low，就處理root的右子樹（因為左子樹一定不符合），返回右子樹的修剪結果，也就是return traversal（root.right）
2. 如果root的val大于high的話，就處理root的左子樹（因為右子樹一定不符合了），返回左子樹修剪之后的結果，也就是return traversal（root.left）
3. 如果root的val處于區間之間，需要修剪他的左右子樹，也就是root.left = traversal(root.left)，右邊子樹同理。
   終止條件：如果為null，返回null

方法一 遞歸法

class Solution(object):def trimBST(self, root, low, high):""":type root: TreeNode:type low: int:type high: int:rtype: TreeNode"""if root == None: return Noneif root.val < low: return self.trimBST(root.right,low,high)if root.val > high:return self.trimBST(root.left,low,high)if root.val<= high and root.val>=low:root.left = self.trimBST(root.left,low,high)root.right = self.trimBST(root.right,low,high)return root

方法二 迭代法

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

本題掌握遞歸法就夠了，遞歸法比較復雜，升級版本；

思路

遞歸三部曲

1. 傳入返回值：傳入的是指向數組的指針，和范圍；函數返回的是由這個范圍內的數組構成的二叉樹的根節點；
2. 終止條件：如果傳入的數組范圍中left>right，那就返回none
3. 單層遞歸邏輯：找到中間節點，作為root，root-left為左邊區間構建的二叉樹，右邊同理

注意點

1. . 為了保證構造的是平衡二叉樹，所以根節點是中間的值
2. . 注意傳入的數組范圍區間：本題中定義的是左閉右閉

方法一 遞歸法

寫代碼注意點：

1. 因為是左閉右閉的，所以判斷迭代終止條件為left大于right
2. 傳入的只是數組，而不是節點，這個要注意

class Solution(object):def traversal(self,left,right):if left > right: return None mid = (left + right)//2node = TreeNode(val = self.nums[mid])node.left = self.traversal(left,mid-1)node.right = self.traversal(mid+1,right)return nodedef sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""self.nums = numsroot = self.traversal(0,len(nums)-1)return root# 精簡版 傳遞切片class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:if not nums:returnmid = len(nums) // 2root = TreeNode(nums[mid])root.left = self.sortedArrayToBST(nums[:mid])root.right = self.sortedArrayToBST(nums[mid + 1 :])return root       

方法二 迭代法

本題迭代法比較困難，就不用放了。

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

題目的意思是：將二叉樹中某節點的新的值為原先樹中大于這個節點的數的值的累加。

思路

總體思路：很簡單，右中左遍歷就行。定義一個全局變量累加

方法一

class Solution(object):def __init__(self):self.count = 0def traversal(self,root):if root == None: return Noneif root.right: self.traversal(root.right)self.count += root.valroot.val = self.countif root.left: self.traversal(root.left)return rootdef convertBST(self, root):""":type root: TreeNode:rtype: TreeNode"""re = self.traversal(root)return re

方法二

---

總結