欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Leetcode学习笔记 二叉搜索树BST

程序员文章站 2022-04-02 11:04:58
二叉搜索树-简介-2验证二叉搜索树,中等注意:不是左子节点和右子节点需要符合,而是左子树和右子树需要符合,所以递归函数需要引入上下界方法一,递归:class Solution: def isValidBST(self, root: TreeNode) -> bool: if not root: return True def fct(node, low, high): if not node:...

二叉搜索树-

简介-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

相关标签: LeetCode学习笔记