代码随想录算法训练营 Day 18
Published:
Q1. LeetCode 669
考虑多种情况：
- 当前节点在范围之内 -> 继续遍历左右子树
- 当前节点小于最小值 -> 遍历右子树并返回新的右子树
- 当前节点大于最大值 -> 遍历左子树并返回新的左子树
解法1. 递归法
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
if root.val < low:
r = self.trimBST(root.right, low, high)
return r
if root.val > high:
l = self.trimBST(root.left, low, high)
return l
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
解法2: 迭代法
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
# 处理头节点
while root and (root.val < low or root.val > high):
if root.val < low:
root = root.right
else:
root = root.left
curr = root
# 头节点已经在范围之内，接下来需要修剪其左子树和右子树
while curr:
while curr.left and curr.left.val < low:
# 左节点值不在范围之内，用左节点的右孩子替换
curr.left = curr.left.right
curr = curr.left
curr = root
while curr:
while curr.right and curr.right.val > high:
# 右节点不在范围之内，用右节点的左孩子替换
curr.right = curr.right.left
curr = curr.right
return root
Q2. LeetCode 108
平衡二叉搜索树，因此取数组的中间元素作为根节点，左为左子树，右为右子树
解法1: 递归法
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
解法2: 迭代法
from collections import deque
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if len(nums) == 0:
return None
root = TreeNode(0) # 初始根节点
nodeQue = deque() # 放遍历的节点
leftQue = deque() # 保存左区间下标
rightQue = deque() # 保存右区间下标
nodeQue.append(root) # 根节点入队列
leftQue.append(0) # 0为左区间下标初始位置
rightQue.append(len(nums) - 1) # len(nums) - 1为右区间下标初始位置
while nodeQue:
curNode = nodeQue.popleft()
left = leftQue.popleft()
right = rightQue.popleft()
mid = left + (right - left) // 2
curNode.val = nums[mid] # 将mid对应的元素给中间节点
if left <= mid - 1: # 处理左区间
curNode.left = TreeNode(0)
nodeQue.append(curNode.left)
leftQue.append(left)
rightQue.append(mid - 1)
if right >= mid + 1: # 处理右区间
curNode.right = TreeNode(0)
nodeQue.append(curNode.right)
leftQue.append(mid + 1)
rightQue.append(right)
return root
Q3. LeetCode 538
累加顺序：右中左，因此按照这个顺序进行遍历，先找到最右节点，然后依次按照反中序遍历进行累加
解法1: 递归法
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
prev = 0
def dfs(node):
if not node:
return
dfs(node.right)
nonlocal prev
node.val += prev
prev = node.val
dfs(node.left)
dfs(root)
return root
解法2: 迭代法 (依然可以采用统一写法，只是需要变换顺序)
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
stack = [root]
prev = 0
while stack:
curr = stack.pop()
if curr:
if curr.left:
stack.append(curr.left) #左
stack.append(curr) #中
stack.append(None)
if curr.right:
stack.append(curr.right)#右
else:
curr = stack.pop()
curr.val += prev
prev = curr.val
return root