[BSearch tree]相关问题
2019-10-20 本文已影响0人
Mree111
Description
把tree变成假链表，即用right可以访问all element
Solution
进行先序遍历，记录之前访问的点，之前访问的点更新left为None, Right为当前节点，接着pre-order遍历（注意保存root.right的值！）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.last_node =None
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return None
if self.last_node:
self.last_node.right=root
self.last_node.left = None
right = root.right
self.last_node=root
self.flatten(root.left)
self.flatten(right)
Description
找最接近的数
Solution
分开为upper bound和lower bound（然后初始化为root的左右node!!），反向更新即可
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
lower = root if root.left is None else root.left
upper = root if root.right is None else root.right
while root:
if target > root.val:
lower = root
root = root.right
elif target <root.val:
upper = root
root = root.left
else:
return root.val
if upper.val - target > target- lower.val:
return lower.val
else:
return upper.val
Description
写一个iterator，使得access next的time最少
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack=[]
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
"""
@return the next smallest number
"""
if len(self.stack)==0:
return None
root = self.stack.pop()
val = root.val
if root.right:
root = root.right
while root:
self.stack.append(root)
root=root.left
return val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return len(self.stack) >0
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
Description
找第K个小的数
Solution
- DFS pre-order遍历
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
def inorder(r):
if r is None:
return []
return inorder(r.left) + [r.val] + inorder(r.right)
return inorder(root)[k - 1]
使用stack遍历，记录所有只访问了左子的点
O(H+k) 因为stack只会进出一次
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
Description
找range [k1,k2]的所有数
Solution
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: param root: The root of the binary search tree
@param k1: An integer
@param k2: An integer
@return: return: Return all keys that k1<=key<=k2 in ascending order
"""
def searchRange(self, root, k1, k2):
# write your code here
self.res=[]
def mid_order(node,k1,k2):
if node is None:
return None
print(node.val,k1,k2)
if node.val<k1:
mid_order(node.right,k1,k2)
if node.val>=k1 and node.val<=k2:
mid_order(node.left,k1,k2)
self.res.append(node.val)
mid_order(node.right,k1,k2)
if node.val>k2:
mid_order(node.left,k1,k2)
mid_order(root,k1,k2)
return self.res
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: param root: The root of the binary search tree
@param k1: An integer
@param k2: An integer
@return: return: Return all keys that k1<=key<=k2 in ascending order
"""
def searchRange(self, root, k1, k2):
# write your code here
self.res=[]
def mid_order(node,k1,k2):
if node is None:
return None
mid_order(node.left,k1,k2)
if node.val>=k1 and node.val<=k2:
self.res.append(node.val)
mid_order(node.right,k1,k2)
mid_order(root,k1,k2)
return self.res
Description
验证二叉树的正确性
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def helper(root,upper,lower):
if root is None:
return True
if root.val <= lower or root.val >= upper:
return False
return helper(root.left,root.val,lower) and helper(root.right,upper,root.val)
return helper(root,float('inf'),float('-inf'))
```
