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
推荐阅读
-
荐 Java刷题笔记15:不同的二叉搜索树( Unique Binary Search Trees)
-
STL源码笔记(17)—二叉排序树BST(C++封装)
-
C++实现LeetCode(109.将有序链表转为二叉搜索树)
-
【leetcode】-700. Search in a Binary Search Tree 查找二叉搜索树
-
LeetCode 426. 将二叉搜索树转化为排序的双向链表(BST中序循环遍历)
-
二叉搜索树(二叉排序树)BST与双向列表的转换
-
LeetCode-1382-将二叉搜索树变平衡-JavaScript
-
leetcode算法练习——不同的二叉搜索树
-
leetcode算法练习——不同的二叉搜索树
-
leetcode 235. 二叉搜索树的最近公共祖先