Leetcode学习笔记 二叉搜索树BST

二叉搜索树-

简介-2

验证二叉搜索树，中等

注意：不是左子节点和右子节点需要符合，而是左子树和右子树需要符合，所以递归函数需要引入上下界
方法一，递归：

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        def fct(node, low, high):
            if not node:
                return True
            if node.val >= high or node.val <= low:
                return False
            return fct(node.left,low,node.val) and fct(node.right,node.val,high)
        return fct(root , -math.inf, math.inf)

方法二，中序遍历：

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        inorder = []
        def dfs(node,inorder):
            if not node:
                return True
            a = dfs(node.left,inorder)
            if not a:
                return False
            if not inorder or node.val > inorder[-1]:	# not inorder 要写在前面，否则会数组越界
                inorder.append(node.val)
            else:
                return False
            b = dfs(node.right,inorder)
            return b
        return dfs(root,inorder)   

二叉搜索树迭代器，中等
说不清楚，看代码吧
等于说模拟了一个递归的过程

class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = []
        self.add_left_order(root)

    def add_left_order(self,node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        smallestnode = self.stack.pop()
        if smallestnode.right:
            self.add_left_order(smallestnode.right)
        return smallestnode.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0

BST中的基本操作

二叉搜索树中的搜索，简单
递归：

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

迭代：

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

二叉搜索树中的插入操作，中等
简单的迭代：

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        node = root
        while node:
            lastnode = node
            if node.val > val:
                node = node.left
            else:
                node = node.right
        if lastnode.val > val:
            lastnode.left = TreeNode(val)
        else:
            lastnode.right = TreeNode(val)
        return root

删除二叉搜索树中的节点，中等
没搜到的不用删
官解用递归做
自己写的，嗯讨论，很长：

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        def connect(father,child,isleft):
            if isleft:
                father.left = child
            else:
                father.right = child
        
        dummy = TreeNode(0,root)
        node = root
        lastnode = dummy
        leftflag = True
        while node:
            if node.val == key:
                break
            elif node.val > key:
                lastnode = node
                node = node.left
                leftflag = True
            else:
                lastnode = node
                node = node.right
                leftflag = False
        #如果没找到值为key的节点，不用删除
        if not node:
            return dummy.left
        if not node.left and not node.right:
            connect(lastnode,None,leftflag)
        elif node.left and node.right:
            nextnode = node.right
            nextlastnode = None
            while nextnode.left:
                nextlastnode = nextnode            
                nextnode = nextnode.left
            if not nextlastnode: #补充的情况
                nextnode.left = node.left
                connect(lastnode,nextnode,leftflag)
                return dummy.left
            if not nextnode.right:
                nextlastnode.left = None
            else:
                nextlastnode.left = nextnode.right
            nextnode.left = node.left
            nextnode.right = node.right
            connect(lastnode,nextnode,leftflag)
        elif node.left:
            connect(lastnode,node.left,leftflag)
        else:
            connect(lastnode,node.right,leftflag)
        return dummy.left

本文地址：https://blog.csdn.net/Li_O_Liu/article/details/110856292