Skip to content

binary_search_tree.md

Latest commit

History

History
176 lines (138 loc) · 5.6 KB

binary_search_tree.md

File metadata and controls

176 lines (138 loc) · 5.6 KB
Raw

二叉搜索树

定义

  • 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
  • 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

应用

validate-binary-search-tree

验证二叉搜索树

classSolution:
defisValidBST(self, root: TreeNode) ->bool:
ifrootisNone:
returnTrues= [(root, float('-inf'), float('inf'))]
whilelen(s) >0:
node, low, up=s.pop()
ifnode.leftisnotNone:
ifnode.left.val<=lowornode.left.val>=node.val:
returnFalses.append((node.left, low, node.val))
ifnode.rightisnotNone:
ifnode.right.val<=node.valornode.right.val>=up:
returnFalses.append((node.right, node.val, up))
returnTrue

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

classSolution:
definsertIntoBST(self, root: TreeNode, val: int) ->TreeNode:
ifrootisNone:
returnTreeNode(val)
ifval>root.val:
root.right=self.insertIntoBST(root.right, val)
else:
root.left=self.insertIntoBST(root.left, val)
returnroot

delete-node-in-a-bst

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

classSolution:
defdeleteNode(self, root: TreeNode, key: int) ->TreeNode:
# try to find the nodedummy=TreeNode(left=root)
parent, node=dummy, rootisleft=TruewhilenodeisnotNoneandnode.val!=key:
parent=nodeisleft=key<node.valnode=node.leftifisleftelsenode.right# if foundifnodeisnotNone:
ifnode.rightisNone:
ifisleft:
parent.left=node.leftelse:
parent.right=node.leftelifnode.leftisNone:
ifisleft:
parent.left=node.rightelse:
parent.right=node.rightelse: p, n=node, node.leftwhilen.rightisnotNone:
p, n=n, n.rightifp!=node:
p.right=n.leftelse:
p.left=n.leftn.left, n.right=node.left, node.rightifisleft:
parent.left=nelse:
parent.right=nreturndummy.left

balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

classSolution:
defisBalanced(self, root: TreeNode) ->bool:
# post-order iteratives= [[TreeNode(), -1, -1]]
node, last=root, Nonewhilelen(s) >1ornodeisnotNone:
ifnodeisnotNone:
s.append([node, -1, -1])
node=node.leftifnodeisNone:
s[-1][1] =0else:
peek=s[-1][0]
ifpeek.rightisnotNoneandlast!=peek.right:
node=peek.rightelse:
ifpeek.rightisNone:
s[-1][2] =0last, dl, dr=s.pop()
ifabs(dl-dr) >1:
returnFalsed=max(dl, dr) +1ifs[-1][1] ==-1:
s[-1][1] =delse:
s[-1][2] =dreturnTrue

valid-bfs-of-bst

给定一个整数数组，求问此数组是不是一个 BST 的 BFS 顺序。

此题是面试真题，但是没有在 leetcode 上找到原题。由于做法比较有趣也很有 BST 的特点，补充在这供参考。

importcollectionsdefbst_bfs(A):
N=len(A)
interval=collections.deque([(float('-inf'), A[0]), (A[0], float('inf'))])
foriinrange(1, N):
whileinterval:
lower, upper=interval.popleft()
iflower<A[i] <upper:
interval.append((lower, A[i]))
interval.append((A[i], upper))
breakifnotinterval:
returnFalsereturnTrueif__name__=="__main__":
A= [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 12]
print(bst_bfs(A))
A= [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 7]
print(bst_bfs(A))

练习