654. 最大二叉树
- 思路
- example
- 递归，前序遍历
- 空节点
- 递归Base case包含空节点
- 或 递归Base case不包含空节点：调用递归函数前需要加判断语句 if root.left:
- 传递数组范围
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def traversal(nums, left, right): # left closed, right closed
if left > right:
return None
val_max, idx_max = -float('inf'), -1
for i in range(left, right+1):
if nums[i] > val_max:
val_max = nums[i]
idx_max = i
node = TreeNode(val_max)
node.left = traversal(nums, left, idx_max - 1)
node.right = traversal(nums, idx_max + 1, right)
return node
return traversal(nums, 0, len(nums)-1)
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
n = len(nums)
if n == 0:
return None
max_ = -float('inf')
idx = -1
for i in range(n):
if nums[i] > max_:
max_ = nums[i]
idx = i
root = TreeNode(nums[idx])
root.left = self.constructMaximumBinaryTree(nums[0:idx])
root.right = self.constructMaximumBinaryTree(nums[idx+1:])
return root
617. 合并二叉树
- 思路
- example
- 把tree2合并到tree1上 (不需要额外构造树)
- if tree1 == None: return tree2 (could be None)
- if tree2 == None: return tree1
- 否则root1.val += root2.val
- 递归，前序遍历 （中序，后序亦可）
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 == None:
return root2
if root2 == None:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 == None:
return root2
if root2 == None:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
- 迭代，层序，deque
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 == None:
return root2
if root2 == None:
return root1
que = collections.deque()
que.append((root1, root2))
while que:
size = len(que)
for _ in range(size):
node1, node2 = que.popleft()
node1.val += node2.val
if node1.left and node2.left: # 两个左节点都非空时才入队列
que.append((node1.left, node2.left))
if node1.right and node2.right: # 两个右节点都非空时才入队列
que.append((node1.right, node2.right))
if node1.left == None and node2.left:
node1.left = node2.left
if node1.right == None and node2.right:
node1.right = node2.right
# 其它不需要处理
return root1
700. 二叉搜索树中的搜索
- 思路
- example
- 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。 - 递归
- Base case：空节点或root.val == val
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root == None:
return None
if root.val == val:
return root
elif root.val < val:
return self.searchBST(root.right, val)
else:
return self.searchBST(root.left, val)
- 迭代 (二分）
- 二叉搜索树：有序。不需要利用栈或队列的帮助就可以实现迭代遍历。
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root:
if root.val == val:
return root
elif root.val < val:
root = root.right
else:
root = root.left
return None
98. 验证二叉搜索树
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
- 思路
- example
- 递归
- 注意搜索树的定义
- 验证左右子树是否搜索树
-
只比较root.val，root.left.val, root.right.val是不够的。下面的递归前序遍历是错误的。还需要验证根节点值小于右子树最小值，大于左子树最大值。
- 上图中，就算右子树改为[6,3,7]也是False.
- 复杂度. 时间：O(n), 空间: O(n)
# 错误代码
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def traversal(root):
if root == None:
return True
if root.left and root.left.val >= root.val:
return False
if root.right and root.right.val <= root.val:
return False
return traversal(root.left) and traversal(root.right)
return traversal(root)
- 递归，中序遍历。BST利用中序遍历就是自然的递增顺序！
- 中序遍历中，如果知道当前节点的pre节点，并且是递增顺序，那么符合要求。
- 最简单的方法，中序遍历得到一个数组，再判断该数组是不是严格递增顺序。
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def traversal(root):
nonlocal pre
if root == None:
return True
flag_left = traversal(root.left)
if flag_left == False:
return False
if pre and root.val <= pre.val:
return False
pre = root
flag_right = traversal(root.right)
if flag_right == False:
return False
return True
pre = None
return traversal(root)
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def traversal(root):
nonlocal pre
if root == None:
return True
if traversal(root.left) == False:
return False
if pre and pre.val >= root.val:
return False
pre = root
if traversal(root.right) == False:
return False
return True
pre = None
return traversal(root)
- 迭代，中序遍历
- cur + stack
- 记录pre 节点或者pre节点的数值。
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
cur = root
stack = []
pre_val = -float('inf')
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre_val >= cur.val:
return False
pre_val = cur.val
cur = cur.right
return True
- 递归，前+后 序，递归函数参数
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def traversal(root, min_val, max_val):
if root == None:
return True
if root.val >= max_val or root.val <= min_val:
return False
valid1 = traversal(root.left, min_val, root.val)
valid2 = traversal(root.right, root.val, max_val)
return valid1 and valid2
return traversal(root, -float('inf'), float('inf'))
- 后序
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def traverse(root):
if root == None:
return True, float('inf'), -float('inf') # !!!
if root.left == None and root.right == None:
return True, root.val, root.val
valid_left, min_left, max_left = traverse(root.left)
if valid_left == False:
return False, min_left, max_left
valid_right, min_right, max_right = traverse(root.right)
if valid_right == False:
return False, min_right, max_right
if max_left < root.val < min_right:
return True, min(min_left, min_right, root.val), max(max_left, max_right, root.val)
return False, min(min_left, min_right, root.val), max(max_left, max_right, root.val)
res, min_, max_ = traverse(root)
return res
