Skip to content

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

二叉搜索树

定义

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

应用

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))

练习

close