JZX轻语：简

LeetCode 700 & 701 - 二叉搜索树的搜索/插入

发表于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

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