*654.最大二叉樹

題目鏈接/文章講解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
視頻講解：https://www.bilibili.com/video/BV1MG411G7ox

• 考點
  • 前序遍歷
  • 構建二叉樹
• 我的思路
  • 參考了力扣題目里的提示
  • 遞歸三要素
    • 形參：數值列表；返回值，當前節點
    • 退出條件：若數值列表為空，返回None
    • 遞歸邏輯
      • 對數值列表求最大值，并基于最大值創建當前節點
      • 利用最大值的索引切割數值列表，并以切割得到的左數值列表作為參數執行左遞歸生成左子樹
      • 利用最大值的索引切割數值列表，并以切割得到的右數值列表作為參數執行右遞歸生成右子樹
• 視頻講解關鍵點總結
  • 和我的思路一致
  • 二叉樹構造類型的問題要使用前序遍歷，先構建中間節點
• 我的思路的問題
  • 無
• 代碼書寫問題
  • 無
• 可執行代碼

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:if not nums:return Noneindex = 0max_value = -1for i in range(len(nums)):if nums[i] > max_value:max_value = nums[i]index = iroot = TreeNode(max_value)root.left = self.constructMaximumBinaryTree(nums[:index])root.right = self.constructMaximumBinaryTree(nums[index + 1:])return root

617.合并二叉樹

題目鏈接/文章講解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
視頻講解：https://www.bilibili.com/video/BV1m14y1Y7JK

• 考點
  • 前序遍歷
  • 二叉樹構建
• 我的思路
  • 遞歸三要素
    • 形參：兩棵樹的當前節點；返回值為新樹的當前節點
    • 退出條件：如果兩棵樹的當前節點均為空，則返回None
    • 遞歸邏輯
      • 由于本題當兩個二叉樹節點狀態不同，執行的邏輯會不同，因此接著退出條件的if繼續寫
      • elif，1號二叉樹節點為空，2號不為空，則當前節點基于2號樹節點創建，同時執行左右遞歸（1號二叉樹的位置直接放None）生成當前節點的左右節點
      • elif，2號二叉樹節點為空，1號不為空，則當前節點基于1號樹節點創建，同時執行左右遞歸（2號二叉樹的位置直接放None）生成當前節點的左右節點
      • else，1號2號都不為空，則當前節點基于二者和創建，同時執行左右遞歸生成當前節點的左右節點
      • 返回當前節點
• 視頻講解關鍵點總結
  • 可以對上述思路進行優化
  • 對于退出條件和兩個elif判斷，可優化為，依次判斷1號樹節點和2號樹節點是否為空，如果1號為空，直接返回2號節點，如果2號為空，直接返回1號節點（因為2者中一旦其一為空，則其后續也為空，此時新樹的后續節點和老樹里不為空的那個完全一致）
• 我的思路的問題
  • 可優化邏輯，優化思路見上
• 代碼書寫問題
  • 無
• 可執行代碼

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if not root1:return root2if not root2:return root1root = TreeNode(root1.val + root2.val)root.left = self.mergeTrees(root1.left, root2.left)root.right = self.mergeTrees(root1.right, root2.right)return root

700.二叉搜索樹中的搜索

題目鏈接/文章講解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html
視頻講解：https://www.bilibili.com/video/BV1wG411g7sF

• 考點
  • 二叉搜索樹的性質
  • 二叉樹遍歷
• 我的思路
  • 直接進行搜索，未利用二叉搜索樹的性質
• 視頻講解關鍵點總結
  • 利用二叉搜索樹的性質
  • 在遞歸邏輯里，當val大于當前節點的值時，向右子樹搜索，小于時，向左子樹搜索
• 我的思路的問題
  • 為考慮二叉搜索樹的性質
• 代碼書寫問題
  • 無
• 可執行代碼

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root is None:return Noneif root.val == val:return rootif root.val > val:return self.searchBST(root.left, val)else:return self.searchBST(root.right, val)

*98.驗證二叉搜索樹

題目鏈接/文章講解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
視頻講解：https://www.bilibili.com/video/BV18P411n7Q4

• 考點
  • 二叉搜索樹的特性
  • 中序遍歷
  • 雙指針
• 我的思路
  • 思路較為混亂
• 視頻講解關鍵點總結
  • 利用中序遍歷和二叉搜索樹的特性，把題目簡化為只需要判斷前序遍歷過程中前后兩個節點是否是后者大于前者即可
  • 一種做法是定義一個額外的數組，在中序遍歷的過程中把所有的值加到數組中，之后判斷數組是否是個遞增數組
  • 第二種做法是在遞歸過程中維護一個表示上一節點值的變量，并在每次遞歸時把當前節點與其相比
  • 第三種做法是雙指針，一個指針指向上一節點，另一指針為當前節點
    • 給Solution類初始化一個pre指針
    • 遞歸三要素
      • 形參：當前節點；返回值為True或False
      • 退出條件：若當前節點為空，return True（因為如果是空二叉樹也是二叉搜索樹）
      • 遞歸邏輯
        • 中序遍歷
        • （左）左遞歸并接收其返回值
        • （中）如果pre指針不為空且當前節點的值小于等于之前指針的值，return False；否則把當前節點賦給pre指針
        • （右）右遞歸并接收其返回值
        • 如果左右遞歸返回值都為True，則返回True，否則返回False
• 我的思路的問題
  • 無思路
• 代碼書寫問題
  • 無
• 可執行代碼

class Solution:def __init__(self):self.pre = Nonedef isValidBST(self, root: Optional[TreeNode]) -> bool:if root is None:return Trueleft = self.isValidBST(root.left)if self.pre is not None and self.pre.val >= root.val:return Falseelse:self.pre = rootright = self.isValidBST(root.right)return left and right