题目简介
110：平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
257：二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
404：左叶子之和
初见思路
- 递归法，直接比较子树的高度，大于1直接返回False，非常慢。
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def get_depth(root:Optional[TreeNode]) -> int:
if not root:
return 0
left_depth = get_depth(root.left)
if left_depth == -1: return -1
right_depth = get_depth(root.right)
if right_depth == -1: return -1
if abs(left_depth - right_depth) > 1:
return -1
return max(get_depth(root.left), get_depth(root.right)) + 1
return False if get_depth(root) == -1 else True
## 迭代法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
height_map = {}
stack = [root]
while stack:
node = stack.pop()
if node:
stack.append(node)
stack.append(None)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
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
257.用栈来迭代，注意一个要点，栈在递归树的时候入栈子节点先右后左，出来的时候顺序才会是左右。
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
stack, path_st, result = [root], [str(root.val)], []
while stack:
cur = stack.pop()
path = path_st.pop()
if not (cur.left or cur.right):
result.append(path)
if cur.right:
stack.append(cur.right)
path_st.append(path + '->' + str(cur.right.val))
if cur.left:
stack.append(cur.left)
path_st.append(path + '->' + str(cur.left.val))
return result
- 递归法很直观
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
value = 0
if root.left and not (root.left.left or root.left.right):
value = root.left.val
return value + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
复盘思路
- 递归法还有更好的写法
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root: return True
return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
self.isBalanced(root.left) and self.isBalanced(root.right)
def depth(self, root):
if not root: return 0
return max(self.depth(root.left), self.depth(root.right)) + 1
257的话还可以迭代回溯，参见回想录的解法。
重点难点
https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html
https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html
今日收获
- 二叉进阶
