代码随想录算法训练营 Day 13
Published:
进一步掌握递归法和迭代法
Q1. LeetCode 110
思路 - 后序遍历
比较节点高度
解法1. 递归法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
return self.getDepth(root, 0)[0]
def getDepth(self, node, depth):
if not node:
return [True, depth]
# 单层判断逻辑：1. 获取当前的左右子树的高度，以及是否平衡；2. 根据左右平衡与左右子树高度确定是否平衡
left_balanced, left_dep = self.getDepth(node.left, depth + 1)
right_balanced, right_dep = self.getDepth(node.right, depth + 1)
balanced = left_balanced and right_balanced and abs(left_dep - right_dep) <= 1
# 返回结果中带有两个变量：是否平衡，最大深度
return [balanced, max(left_dep, right_dep)]
解法2: 迭代法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
height_map = {}
stack = [root]
while stack:
# 利用None值做标记，只有遇到None值，下一个节点才是需要处理的节点
node = stack.pop()
if node:
stack.append(node)
stack.append(None)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
else:
real_node = stack.pop()
left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)
if abs(left - right) > 1:
return False
height_map[real_node] = 1 + max(left, right)
return True
Take some notes
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。（通常使用前序遍历）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。（通常使用后序遍历）
Q2. LeetCode 257
思路 - 前序遍历
父节点指向子节点
解法1: 递归+回溯
注意：递归的终止条件，回溯的使用方法。回溯和递归是一一对应的，有一个递归，就要有一个回溯
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
def dfs(node, lst):
lst.append(node.val)
# 终止条件：找到叶子节点
if not node.left and not node.right:
path = '->'.join(str(n) for n in lst)
res.append(path)
return
if node.left:
dfs(node.left, lst)
lst.pop()
if node.right:
dfs(node.right, lst)
lst.pop()
dfs(root, [])
return res
解法2: 迭代法 (理解)
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
stack = [root]
path = [str(root.val)]
res = []
while stack:
curr = stack.pop()
p = path.pop()
if not curr.left and not curr.right:
res.append(p)
if curr.right:
stack.append(curr.right)
path.append(p + '->' + str(curr.right.val))
if curr.left:
stack.append(curr.left)
path.append(p + '->' + str(curr.left.val))
return res
Q3. LeetCode 404
思路 - 后序遍历
这样才能把左右子树中的值找到后，然后在父节点处求和
解法1: 递归法
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
# 当前节点为空节点
if not root:
return 0
# 当前节点为叶子节点
if not root.left and not root.right:
return 0
left_value = self.sumOfLeftLeaves(root.left)
if root.left and not root.left.left and not root.left.right:
left_value = root.left.val
right_value = self.sumOfLeftLeaves(root.right)
return left_value + right_value
解法2: 迭代法
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
res = 0
if not root:
return 0
stack = [root]
while stack:
curr = stack.pop()
if curr.left and not curr.left.left and not curr.left.right:
res += curr.left.val
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return res
也可以添加一个标签，判断当前节点是否为左节点
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
res = 0
if not root:
return 0
stack = [(root, False)]
while stack:
curr, is_left = stack.pop()
if is_left and not curr.left and not curr.right:
res += curr.val
if curr.right:
stack.append((curr.right, False))
if curr.left:
stack.append((curr.left, True))
return res
Q4. LeetCode 222
思路 - 后序遍历
先求左右子树中节点数量，再加1（父节点）即为总数量
解法1: 递归法
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
left_num = dfs(node.left)
right_num = dfs(node.right)
return left_num + right_num + 1
res = dfs(root)
return res
利用完全二叉树的性质：1. 找到其中的满二叉子树；2. 利用公式计算满二叉子树的节点数量；3. 最后加1得到总节点数量
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
left_depth, right_depth = 0, 0
l = node.left
r = node.right
while l:
l = l.left
left_depth += 1
while r:
r = r.right
right_depth += 1
# 假如两者深度一样，那么找到了一个满二叉（子）树，该树节点数量总共为2^d - 1
if left_depth == right_depth:
return (2 << left_depth) - 1
return dfs(node.left) + dfs(node.right) + 1
res = dfs(root)
return res
解法2: 迭代法 (层序遍历)
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([root])
res = 0
while queue:
for _ in range(len(queue)):
curr = queue.popleft()
res += 1
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
return res