[数据结构与算法]LeetCode--二叉搜索树基本操作--搜索、增、删、判断

LeetCode–二叉搜索树基本操作–搜索、增、删、判断

二叉搜索树BST的定义：一个二叉树中，任意节点的值要大于左子树所有节点的值，且要小于右子树所有节点的值。

二叉树算法的设计路线：递归思想，明确一个节点要做的事情，然后剩下的事情交给框架

BST的基础操作：判断BST的合法性、增、删、改、查，其中删除及判断合法性的操作略微复杂。

题目链接：
700. 二叉搜索树中的搜索
100. 相同的树
701. 二叉搜索树中的插入操作
450. 删除二叉搜索树中的节点
98. 验证二叉搜索树

递归三部曲

1、递归函数的参数与返回值：
参数，根结点+目标值（例如：删除、插入的目标值）
返回值，当遍历整棵树时不需要返回值，如果是要求搜索到符合条件的值就返回，则需要及时返回值。

2、递归终止条件：
一般为遍历到根结点为空作为终止条件

3、单层递归逻辑：
满足条件及返回，不满足条件则继续遍历左右子树

700、 二叉搜索树中的搜索

题目描述：给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

递归法：

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        # 分为两种情况，一种是没有找到该结点，返回null，另一种是找到该结点，返回以该结点为根的子树
        if not root:
            return root
        
        if root.val == val:   # 中,如果相等，返回子树
            return root 
        if root.val > val:# 左递归
            return self.searchBST(root.left, val)
        if root.val < val:# 右递归
            return self.searchBST(root.right, val)

迭代法：

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向.

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root is not None:
            if root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right
            else:
                return root
        return root

100、相同的树

题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路：考虑所有的情况，为空的情况

• 首先，如果两个树都为空的话，两个树肯定相同，若两个树有一个为空，两个树都不相同；
• 接下来考虑两个树都不为空的情况，先判断根结点，如果根结点都不相同，那两个树肯定不同，这就是单层递归逻辑；
• 再分别判断左子树和右子树是否相同。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 考虑所有的情况，为空的情况
        # 首先，如果两个树都为空的话，两个树肯定相同，若两个树有一个为空，两个树都不相同
        if not p and not q:
            return True
        elif not p or not q:
            return False

        # 接下来考虑两个树都不为空的情况，先判断根结点，如果根结点都不相同，那两个树肯定不同，这就是单层递归逻辑，再分别判断左子树和右子树是否相同，这就开始用到递归了
        elif p.val != q.val:
            return False
        else:    
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

注：一般写if语句的时候先判断不满足条件的，最后返回满足条件的

701、二叉搜索树中的插入操作

题目描述：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要在插入后仍保持为二叉搜索树即可。可以返回任意有效的结果 。

Python代码实现：

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        # 先找到插入位置再操作
        # 最常规的插入，首先遍历树的根结点，看看与根结点相比，大于根结点向右遍历，小于根结点向左遍历
        # 递归终止条件，遍历到根结点为空
        if not root:
            return TreeNode(val)   # 新建一个以val为值的节点

        if root.val > val:    # 左递归
            root.left = self.insertIntoBST(root.left, val)
        if root.val < val:    # 右递归
            root.right = self.insertIntoBST(root.right, val)
        return root

注意：遍历到根结点为空，不能直接插入值，要新建一个结点储存要插入的值，最后返回整个树

450、删除二叉搜索树中的结点

平衡二叉树中删除结点遇到的各种情况：

• 第一种：没找到删除的结点，遍历到空结点就直接返回了；
• 找到删除的结点：
  • 第二种：左右孩子都为空，直接删除结点，返回NULL为根结点；
  • 第三种：删除结点的左孩子为空，右孩子不为空=，删除结点，右孩子直接补位，返回右孩子为根结点；
  • 第四种：删除结点的右孩子为空，左孩子不为空，删除结点，左孩子直接补位，返回左孩子为根结点；
  • 第五种：删除结点的左右孩子都不为空，可以选择将左孩子移到右孩子中最小值的左边，或者把右孩子移到左孩子中最大值的右边。

可以自己画一下图示：

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        # 五种情况：
        # 1）没有找到删除结点
        if not root:
            return root
        # 2）删除结点没有左右孩子，直接返回None；
        if root.val == key:
            if not root.left and not root.right:
                del root
                return None
        # 3）删除结点有左孩子，没有右孩子，直接删除，让根结点指向左孩子，即直接返回孩子
            elif root.left and not root.right:
                temp = root
                root = root.left
                del temp
                return root
        # 4）删除结点有右孩子，没有左孩子，直接删除，让根结点指向右孩子，即直接返回孩子
            elif not root.left and root.right:
                temp = root
                root = root.right
                del temp
                return root
        # 5）若删除结点既有左孩子也有右孩子：涉及结点选择哪一个孩子，一直遍历到左孩子（向右遍历）中最大的，或者右孩子（向左遍历）中最小的作为结点，把另一侧直接添加到这个值后面
            else:
                v = root.right    # 将右孩子赋值给v结点
                # 遍历删除结点的右子树，直到找到最小值（最小值都在左边，所以要遍历左边）
                while v.left:
                    v = v.left  
                v.left = root.left   # 左子树的值挪到这个最小值左边
                temp = root
                root = root.right    #右边直接补位，给根结点
                del temp
                return root
        # 开始整个树的遍历，找到删除结点
        # 如果遍历到一个结点，发现这个结点比删除的值要大，就可以直接向左遍历了
        if root.val > key:  
            root.left = self.deleteNode(root.left, key)
        # 如果遍历到一个结点，发现这个结点比删除的值要小，就可以直接向右遍历了
        if root.val < key:  
            root.right = self.deleteNode(root.right, key)
        return root     

98、验证二叉搜索树

验证二叉搜索树，首先二叉搜索树的特点：

1. 节点的左?树只包含?于当前节点的数。
2. 节点的右?树只包含?于当前节点的数。
3. 所有左?树和右?树?身必须也是?叉搜索树。

如果只是单纯的利用左结点的值小于中间结点且中间结点的值小于右结点的值，会导致以下情况：
即不能满足所有左子树的值都小于根结点，所有右子树的值都大于根结点

解题思路：

• 中序遍历输出的二叉搜索树节点的数值是有序序列
• 利用中序遍历所有值，再验证这个数组是否为一个有序数组，且保证不能有重复值

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 递归函数定义，参数：树的根结点，返回值，有序数组
        # 递归函数终止条件，一直遍历直到最后的叶子节点，即root为空
        # 单层递归逻辑，中序遍历，得到一个有序数组
        res = []
        def buildalist(root):
            if not root:
                return
            # 中序遍历
            buildalist(root.left)
            res.append(root.val)
            buildalist(root.right)
            return res
        buildalist(root)

        return sorted(res) == res and len(set(res)) == len(res)   # 判断有序且无重复元素

sorted排序，set() 函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。