same tree - 检查两个是不是一样，如果一个是空的肯定是false
tree path - 检查root是否有left和right，没有加到paths里
tricky的
next largest after p - 当大于或等于p时看右边，else看左边
在左边的时候有两种scenario
no more left child so return the p’s parent
more left return it’s right -> which is ans
1 2 3 4 5 6 7 8
|
nextLargest(p): if not root: return None if root.val<p.val: #go to the right return nextLargest(root.right, p) else: ans = nextLargest(root.left, p) return ans if ans or root
|
问题
算第K大个BST的node - 用reverse inorder，然后在第k个时停掉
Check for valid BST - 设个min和max来确定每个tree是跟root在比
1 2 3 4 5 6
|
if not root: return True #given case if root.val >= max or root.val <= min: #equal means false return False return dfs(root.left, min, root.val) and dfs(root.right, root.val, max)
|
类似的题
算closest bst value to target - update一个global mindiff和maxnode
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
self.mindiff = float('inf') self.maxnode = None self.dfs(root, target) return self.maxnode.val def dfs(self, root, target): if not root: return None #does not matter if abs(root.val*1.0-target)<mindiff: mindiff = abs(root.val*1.0-target) maxnode = root self.dfs(root.left, target) self.dfs(root.right, target)
|
近期评论