669_修剪二叉搜索树

类型：树

• 669. 修剪二叉搜索树 💛

  https://leetcode-cn.com/problems/trim-a-binary-search-tree/

  ❓ 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。不得破坏留在树中的结点的相对结构。

  💡 递归

  我们要利用好其搜索树的性质。

  • 如果结点值大于 high，我们就完全抛弃右子树，直接递归左子树
  • 如果结点值小于 low，我们就完全抛弃左子树，完全递归右子树
  • 如果结点值在 [low, high] 之间，则两个子树都要递归，并且要完成递归修剪后的拼接

  class Solution(object):
      def trimBST(self, root, L, R):
          def trim(node):
              if not node:
                  return None
              elif node.val > R:
                  return trim(node.left)
              elif node.val < L:
                  return trim(node.right)
              else:
                  node.left = trim(node.left)
                  node.right = trim(node.right)
                  return node
  
          return trim(root)

  时间复杂度：O(n)，空间复杂度：O(n)