【刷题DAY23】669, 108, 538.md

669. 修剪二叉搜索树

题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

• https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E9%80%92%E5%BD%92%E6%B3%95

0x4 看完代码随想录之后的想法

• 二叉搜索树删除节点，保留原节点

  class Solution:
      def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
          if not root:
              return root
          # 函数输入root，输出符合条件的节点头
          
          # 当前节点的值在[low, high]区间左侧，说明符合条件的头节点要去右侧寻找，并直接返回！！等价于删掉了当前节点
          if(root.val < low):
              return self.trimBST(root.right, low, high)
          # 当前节点的值在[low, high]区间右侧，说明符合条件的头节点要去左侧寻找，并直接返回！！等价于删掉了当前节点
          elif(root.val > high):
              return self.trimBST(root.left, low, high)
          # 如果这两个都没进去，说明root.val在[low, high]的区间里面，当前的节点也是合理的这个节点不能删，所以要用本节点root.left root.right接住
          root.left = self.trimBST(root.left, low, high)
          root.right = self.trimBST(root.right, low, high)
          return root

0x5 今日收获，记录一下自己的学习时长

• 1.5h

---

108.将有序数组转换为二叉搜索树

题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

• https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E9%80%92%E5%BD%92

0x4 看完代码随想录之后的想法

• 类似前（后）序和中序构造二叉树，寻找切割点

0x5 今日收获，记录一下自己的学习时长

• 45min

---

538. 把二叉搜索树转换为累加树

题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

• https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html

0x4 看完代码随想录之后的想法

• 需要两个指针，pre和cur，pre全局遍历变量，记录前一个节点的值
• 遍历顺序：右中左

0x5 今日收获，记录一下自己的学习时长

• 1h

---

待重点复习

669, 108, 538

总结

• 二叉搜索树删除节点，保留原节点
• 将有序数组转换为二叉搜索树
  • 切割点
• 把二叉搜索树转换为累加树
  • 右中左
  • pre，cur