发表于 2024.04.17

• 二叉搜索树(BST)的模板题，均可以使用一个函数递归实现。插入方法是搜索方法的一个扩展情况：如果当前节点为空，则新建一个节点并返回；递归遍历的时候，都需要重新设置下左/右孩子，并返回自身。这是大二数据结构课本的一个做法，不得不说确实挺妙的，很好地体现递归的特点。

  此外，由于BST的遍历是单方向的，可以很容易地将递归改为循环的方式。类似于链表的遍历，使用一个dummy头节点来保证算法的一致性即可。

  BST的搜索算法：

  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  
  
  class Solution:
      def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
          if root is None or root.val == val:
              return root
          if root.val < val:
              return self.searchBST(root.right, val)
          return self.searchBST(root.left, val)

  搜索算法的非递归形式：

  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  
  
  class Solution:
      def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
          curr = root
          while curr is not None:
              if curr.val == val:
                  return curr
              if val < curr.val:
                  curr = curr.left
              else:
                  curr = curr.right
          return curr

  BST的插入算法：

  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  
  
  class Solution:
      def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
          if root is None:
              return TreeNode(val)
          if root.val > val:
              root.left = self.insertIntoBST(root.left, val)
          else:
              root.right = self.insertIntoBST(root.right, val)
          return root

  插入算法的非递归形式：

  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  
  
  class Solution:
      def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
          dummy_root = TreeNode(-1, root)
          prev, curr = dummy_root, root
          is_prev_lc = True
          while curr is not None:
              prev = curr
              curr, is_prev_lc = (curr.left, True) if val < curr.val else (curr.right, False)
          new_node = TreeNode(val)
          if is_prev_lc:
              prev.left = new_node
          else:
              prev.right = new_node
          return dummy_root.left

• LC 题目链接