代码随想录算法训练营 Day 15
Published:
Q1. LeetCode 654
思路 - 前序遍历
先构造中间节点，然后根据划分递归构造左子树和右子树
解法1. 递归+回溯
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
max_val = max(nums)
root = TreeNode(max_val)
separator_idx = nums.index(max_val)
left_nums = nums[:separator_idx]
right_nums = nums[separator_idx + 1:]
root.left = self.constructMaximumBinaryTree(left_nums)
root.right = self.constructMaximumBinaryTree(right_nums)
return root
Q2. LeetCode 617
思路 - 任何遍历方式都可以
解法1: 递归法
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
解法2: 迭代法
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
queue = deque([root1, root2])
while queue:
node1 = queue.popleft()
node2 = queue.popleft()
node1.val += node2.val
if node1.left and node2.left:
queue.append(node1.left)
queue.append(node2.left)
if node1.right and node2.right:
queue.append(node1.right)
queue.append(node2.right)
if not node1.left and node2.left:
node1.left = node2.left
if not node1.right and node2.right:
node1.right = node2.right
return root1
Q3. LeetCode 700
解法1: 递归法
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if root.val < val:
return self.searchBST(root.right, val)
if root.val > val:
return self.searchBST(root.left, val)
解法2: 迭代法
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root:
if root.val < val:
root = root.right
elif root.val > val:
root = root.left
else:
return root
return None
二叉搜索树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
Q4. LeetCode 98
思路 - 中序遍历
二叉搜索树必须保证左 < 中 < 右，因此中序遍历可以按照左中右的顺序确定是否为二叉搜索树
解法1: 递归法 - 得到中序遍历结果，判断是否为递增数组
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
arr = []
def dfs(node):
if not node:
return
dfs(node.left)
arr.append(node.val)
dfs(node.right)
dfs(root)
for i in range(1, len(arr)):
if arr[i] <= arr[i - 1]:
return False
return True
解法2: 递归法
class Solution:
def __init__(self):
self.pre = None
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
left_valid = self.isValidBST(root.left)
# 当前节点的值一定大于之前节点的值。注意要判断条件，值可能为0或者负数
if self.pre is not None and self.pre >= root.val:
return False
# 存储当前节点的值
self.pre = root.val
right_valid = self.isValidBST(root.right)
return left_valid and right_valid
解法3: 迭代法
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
pre = None
stack = [root]
while stack:
curr = stack.pop()
if curr:
if curr.right:
stack.append(curr.right)
stack.append(curr)
stack.append(None)
if curr.left:
stack.append(curr.left)
else:
curr = stack.pop()
if pre and pre.val >= curr.val:
return False
pre = curr
return True