面试题 04.06. 后继者
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
ans = None
cur = root
while cur:
if cur.val <= p.val:
cur = cur.right
else:
ans = cur
cur = cur.left
return ans
450. 删除二叉搜索树中的节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def predeccessor(self, root):
temp = root.right
while temp.left: temp = temp.left
return temp
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root: return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
if not root.left or not root.right:
return root.left if root.left else root.right
else:
temp = self.predeccessor(root)
root.val = temp.val
root.right = self.deleteNode(root.right, temp.val)
return root
1382. 将二叉搜索树变平衡
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, nodes, l, r):
if l > r: return None
mid = (l + r) // 2
root = nodes[mid]
root.left = self.buildTree(nodes, l, mid - 1)
root.right = self.buildTree(nodes, mid + 1, r)
return root
def inorder(self, root, ans):
if not root: return
self.inorder(root.left, ans)
ans.append(root)
self.inorder(root.right, ans)
return
def balanceBST(self, root: TreeNode) -> TreeNode:
nodes = []
self.inorder(root, nodes)
return self.buildTree(nodes, 0, len(nodes) - 1)
108. 将有序数组转换为二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums: return None
mid = (len(nums) - 1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+ 1:])
return root
98. 验证二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorder(self, root):
if not root: return True
if not self.inorder(root.left): return False
if self.pre and self.pre.val >= root.val:
return False
self.pre = root
if not self.inorder(root.right): return False
return True
def isValidBST(self, root: Optional[TreeNode]) -> bool:
self.pre = None
return self.inorder(root)
501. 二叉搜索树中的众数
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorder(self, root, res):
if not root: return
self.inorder(root.left, res)
if self.pre.val == root.val:
self.cur_count += 1
else:
self.cur_count = 1
self.pre = root
if self.max_count == self.cur_count:
res.append(root.val)
elif self.max_count < self.cur_count:
self.max_count = self.cur_count
res *= 0
res.append(root.val)
self.inorder(root.right, res)
return
def findMode(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.cur_count = 0
self.max_count = 0
self.pre = root
self.inorder(root, res)
return res
面试题 17.12. BiNode
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorder(self, root):
if not root: return
self.inorder(root.left)
root.left = None
self.pre.right = root
self.pre = root
self.inorder(root.right)
def convertBiNode(self, root: TreeNode) -> TreeNode:
head = TreeNode(0)
self.pre = head
self.inorder(root)
return head.right
剑指 Offer 33. 二叉搜索树的后序遍历序列
class Solution:
def inorder(self, nums, l, r):
if l > r: return True
mid = l
while nums[mid] < nums[r]: mid += 1
if not self.inorder(nums, l, mid - 1):
return False
if self.pre != -1 and nums[self.pre] > nums[r]:
return False
self.pre = r
if not self.inorder(nums, mid, r - 1):
return False
return True
def verifyPostorder(self, postorder: List[int]) -> bool:
self.pre = -1
return self.inorder(postorder, 0, len(postorder) - 1)
1008. 前序遍历构造二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildtree(self, nums):
if len(nums) <= 0: return None
mid = 1
while len(nums) > mid and nums[mid] < nums[0]: mid += 1
root = TreeNode(nums[0])
root.left = self.buildtree(nums[1: mid])
root.right = self.buildtree(nums[mid:])
return root
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
return self.buildtree(preorder)
面试题 04.09. 二叉搜索树序列
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def fun1(self, s1, s2):
if not s1: return [s2]
if not s2: return [s1]
result = []
for data in self.fun1(s1[1:], s2):
result.append([s1[0]] + data)
for data in self.fun1(s1, s2[1:]):
result.append([s2[0]] + data)
return result
def merge(self, left, right):
result = []
for l in left:
for r in right:
result.extend(self.fun1(l, r))
return result
def BSTSequences(self, root: TreeNode) -> List[List[int]]:
if not root: return [[]]
left = self.BSTSequences(root.left)
right = self.BSTSequences(root.right)
return [[root.val] + data for data in self.merge(left, right)]
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76877.html
