96 Unique Binary Search Trees
'''
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
'''
class Solution:
def numTrees(self, n: int) -> int:
f = [0 for _ in range(n+1)]
f[0] = 1
f[1] = 1
for i in range(2, n+1):
for k in range(i+1):
f[i] += f[i-k] * f[k-1]
return f[n]
98 Validate Binary Search Tree
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def check(cur, left_limit, right_limit):
if not cur:
return True
if left_limit < cur.val and cur.val < right_limit:
return check(cur.left, left_limit, cur.val) and check(cur.right, cur.val, right_limit)
return False
return check(root, -1*float("inf"), float("inf"))
99 Recover Binary Search Tree
'''
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Input: [1,3,null,null,2]
1
/
3
\
2
Output: [3,1,null,null,2]
3
/
1
\
2
'''
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
# [1, 2, 3, 4, 5, 6] ==> [1, 5, 3, 4, 2, 6]
# 保存遍历当前节点的前继节点
self.pre, self.first, self.second = None, None, None
self.inorder(root)
self.first.val, self.second.val = self.second.val, self.first.val
def inorder(self, root):
if not root:
return
self.inorder(root.left)
if self.pre and self.pre.val > root.val:
if not self.first:
self.first = self.pre
self.second = root
self.pre = root
self.inorder(root.right)
100 Same Tree
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not p and not q:
return True
elif p and not q:
return False
elif not p and q:
return False
else:
if p.val != q.val:
return False
else:
x = False
y = False
x = self.isSameTree(p.left, q.left)
y = self.isSameTree(p.right, q.right)
return x & y
101 Symmetric Tree
'''
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
'''
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.mirror(root.left, root.right)
def mirror(self, left, right):
if not left or not right:
return left == right
if left.val != right.val:
return False
return self.mirror(left.right, right.left) and self.mirror(left.left, right.right)
102. Binary Tree Level Order Traversal
'''
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
'''
class Solution:
# # BFS
# def levelOrder(self, root: TreeNode) -> List[List[int]]:
# if root is None:
# return []
# result = []
# curlevel = [root]
# nextlevel = []
# res = []
# while curlevel:
# node = curlevel.pop(0)
# if node.left:
# nextlevel.append(node.left)
# if node.right:
# nextlevel.append(node.right)
# res.append(node.val)
# if not curlevel:
# curlevel, nextlevel = nextlevel, []
# result.append(res)
# res = []
# return result
# DFS
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
self.result = []
self._dfs(root, 0)
return self.result
def _dfs(self, node, level):
if not node:
return
if len(self.result) < level + 1:
self.result.append([])
self.result[level].append(node.val)
self._dfs(node.left, level+1)
self._dfs(node.right, level+1)
104 Maximum Depth of Binary Tree
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return max(left, right)+1
111 Minimum Depth of Binary Tree
class Solution:
# BFS
'''
def minDepth(self, root: TreeNode) -> int:
if not root :
return 0
def isleaf(node):
if (not node.left and not node.right):
return True
return False
queue = [root]
count = 0
while queue:
nextlevel = []
for i in range(len(queue)):
node = queue.pop(0)
if isleaf(node):
return count + 1
if node.left:
nextlevel.append(node.left)
if node.right:
nextlevel.append(node.right)
if queue == [] and nextlevel:
count += 1
queue = nextlevel
'''
# DFS
def minDepth(self, root: TreeNode) -> int:
if not root :
return 0
dleft = self.minDepth(root.left)
dright = self.minDepth(root.right)
if root.left and root.right:
return 1 + min(dleft, dright)
if dleft > dright:
return dleft + 1
else:
return dright + 1
112 Path Sum
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root is None:
return False
return self.dfs(root, sum)
def dfs(self, root, target):
if not root.left and not root.right:
if target == root.val:
return True
if root.left:
if self.dfs(root.left, target-root.val):
return True
if root.right:
if self.dfs(root.right, target-root.val):
return True
return False
113. Path Sum II
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if root is None:
return []
self.res = []
self.dfs(root, sum, [])
return self.res
def dfs(self, root, target, tmp):
if not root.left and not root.right:
if target == root.val:
tmp.append(root.val)
self.res.append(tmp)
return
if root.left:
self.dfs(root.left, target-root.val, tmp+[root.val])
if root.right:
self.dfs(root.right, target-root.val, tmp+[root.val])
return
124 Binary Tree Maximum Path Sum
'''
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
'''
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
if root is None:
return 0
self.maxsum = root.val
def solve(root): # 以root为起始的最长path sum
if root is None:
return 0
sum_, l, r = root.val, 0, 0
if root.left:
l = solve(root.left)
if l > 0: sum_ += l
if root.right:
r = solve(root.right)
if r > 0: sum_ += r
self.maxsum = max(self.maxsum, sum_)
return max(root.val, root.val+l, root.val+r)
solve(root)
return self.maxsum
226 Invert Binary Tree
'''
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
'''
class Solution:
'''
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
'''
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
235 Lowest Common Ancestor of a Binary Search Tree
image
'''
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
'''
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 递归
# if root is None:
# return None
# if p.val < root.val and root.val > q.val:
# return self.lowestCommonAncestor(root.left, p, q)
# if p.val > root.val and root.val < q.val:
# return self.lowestCommonAncestor(root.right, p, q)
# return root
# 非递归
while root:
if p.val < root.val > q.val:
root = root.left
elif p.val > root.val < q.val:
root = root.right
else:
return root
return None
236 Lowest Common Ancestor of a Binary Tree
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None:
return None
if root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
elif not left and right:
return right
else:
return left
257 Binary Tree Paths
'''
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
'''
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if root is None:
return []
path = str(root.val)
res = []
self.traverse(root,path,res)
return res
def traverse(self, root, path, res):
if root.left is None and root.right is None:
res.append(path)
if root.left is not None:
self.traverse(root.left, path+"->"+str(root.left.val), res)
if root.right is not None:
self.traverse(root.right, path+"->"+str(root.right.val), res)
网友评论