笔记：自底向上的递归技巧
LeetCode 0110 平衡二叉树 (简单, 2022-02)LeetCode 0124 二叉树中的最大路径和 (困难, 2022-02)LeetCode 0337 打家劫舍III (中等, 2022-02)LeetCode 0437 路径总和III (中等, 2022-02)剑指Offer 6802 二叉树的最近公共祖先 (简单, 2022-01)牛客 0060 判断一棵二叉树是否为搜索二叉树和完全二叉树 (中等, 2022-03)
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。- 考虑对以 X 为头结点的树，为了确定其是否为平衡二叉树，需要从左右子树获取哪些信息？
- 根据定义，显然需要知道两个信息：
- 子树是否为平衡二叉树（
is_balanced: bool）； - 子树的高度（
height: int）；
- 子树是否为平衡二叉树（
- 假设子树的这些信息已知，怎么求 X 节点的上述信息：
x_is_balanced = l.is_balanced and r.is_balanced and abs(l.height - r.height) <= 1即左右子树都平衡，且高度差小于等于 1
x_height = max(l.height, r.height) + 1
- 对空节点，有：
is_balanced = True height = 0
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
from collections import namedtuple
# 用一个结构来组织需要的信息，可以直接用 tuple，这里是为了更直观
Info = namedtuple('Info', ['is_balanced', 'height'])
def dfs(x):
if not x: # 空节点
return Info(True, 0)
l, r = dfs(x.left), dfs(x.right)
is_balanced = l.is_balanced and r.is_balanced and abs(l.height - r.height) <= 1
height = max(l.height, r.height) + 1
return Info(is_balanced, height)
return dfs(root).is_balanced # 返回需要的信息
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。- 考虑对以 X 为头结点的树，为了求得最大路径和，需要从左右子树获取哪些信息？
- 根据要求，显然需要知道：
- 子树能提供的最大和路径，即以子树节点为终点的最大路径，记
h: int；为什么需要这个信息：为了计算经过 X 节点的最大路径，这条路径的特点是：从某一节点出发到达子树节点，经过 X 节点后，再进入另一个子节点的最大和路径；
这是本题除 coding 外最大的难点，能想出这个信息也就基本解决这个问题了；
- 子树中的最大路径和（即子问题）：为了比较得出全局最大路径和，记
s: int；
- 子树能提供的最大和路径，即以子树节点为终点的最大路径，记
- 假设子树的这些信息已知，怎么求 X 节点的上述信息：
x_h = x.val + max(0, l.h, r.h)因为需要经过 X 节点，所以必须加上 x.val，同时如果左右子树提供的 h 小于 0，那么不如舍去；
x_s = max(l.s, r.s, max(l.h, 0) + max(r.h, 0) + x.val)这一步容易写成
x_s = max(l.s, r.s, x_h)或者x_s = max(l.s, r.s, l.h + r.h + x.val)，都是对问题理解不到位；
重申：模板只是帮我们解决怎么组织代码的问题，而写出正确的代码一靠观察，二靠积累；
- 对空节点，有：
h = 0 s = -inf # 因为题目要求至少包含一个节点，如果设为 0，那么当所有节点为负数时，就会出错
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
from dataclasses import dataclass
@dataclass
class Info:
h: int # 该节点能提供的最大路径（含节点本身）
s: int # 该节点下的最大路径（可能不包含该节点）
# 事实上 Info 里的 s 完全可以用一个全局变量来代替，这里是为了尽量拟合模板；熟练之后就不必这么做了。
def dfs(x):
if not x:
# 对空节点，初始化 h=0, s=负无穷
return Info(0, float('-inf'))
l, r = dfs(x.left), dfs(x.right)
x_h = x.val + max(0, l.h, r.h)
x_s = max(l.s, r.s, max(l.h, 0) + max(r.h, 0) + x.val)
return Info(x_h, x_s)
return dfs(root).s
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。- 树形 DP 问题，就是否抢劫当前节点分两种情况讨论，详见代码；
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: TreeNode) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x):
# 空节点
if not x: return 0
# 叶节点
if not x.left and not x.right: return x.val
# 不抢当前节点
r1 = dfs(x.left) + dfs(x.right)
# 抢当前节点
r2 = x.val
if x.left:
r2 += dfs(x.left.left) + dfs(x.left.right)
if x.right:
r2 += dfs(x.right.left) + dfs(x.right.right)
return max(r1, r2)
return dfs(root)
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。- 先序遍历每个节点，每个节点再先序遍历找目标值；
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int: # noqa
""""""
if root is None:
return 0
def dfs(x, rest):
if not x:
return 0
ans = 0 if x.val != rest else 1 # 如果相等说明，从头结点开始到该节点可以形成一条路径
# 继续遍历左右子树
rest -= x.val
ans += dfs(x.left, rest)
ans += dfs(x.right, rest)
rest += x.val # 回溯
return ans
# dfs 是一个先序遍历
ret = dfs(root, targetSum)
# pathSum 本身也是一个先序遍历，相当于对每个点都做一次 dfs
ret += self.pathSum(root.left, targetSum)
ret += self.pathSum(root.right, targetSum)
return retPython
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
from collections import defaultdict
self.prefix = defaultdict(int) # 保存前缀和
self.prefix[0] = 1
self.targetSum = targetSum
def dfs(x, preSum):
if not x: return 0
ret = 0
preSum += x.val
ret += self.prefix[preSum - targetSum]
self.prefix[preSum] += 1
ret += dfs(x.left, preSum)
ret += dfs(x.right, preSum)
self.prefix[preSum] -= 1
return ret
return dfs(root, 0)Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
from collections import defaultdict
self.prefix = defaultdict(int) # 保存前缀和
self.prefix[0] = 1
self.targetSum = targetSum
def dfs(x, preSum):
if not x: return 0
ret = 0
preSum += x.val
ret += self.prefix[preSum - targetSum]
self.prefix[preSum] += 1
ret += dfs(x.left, preSum)
ret += dfs(x.right, preSum)
self.prefix[preSum] -= 1
return ret
return dfs(root, 0)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。详细描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 记录 p, q 从上到下的路径，路径中最后一个相同节点即答案；
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
# 后序遍历记录所有祖先
def dfs(node, target, trace):
if node is None:
return False
# 注意自己也是自己的祖先
if node.val == target.val or dfs(node.left, target, trace) or dfs(node.right, target, trace):
trace.append(node)
return True
else:
return False
# 分别找出 p 和 q 的祖先路径
trace_p = []
dfs(root, p, trace_p)
# print(trace_p)
trace_q = []
dfs(root, q, trace_q)
# print(trace_q)
# 遍历找出最后一个相同的祖先
ret = None
for l, r in zip(trace_p[::-1], trace_q[::-1]):
if l.val == r.val:
ret = l
else:
break
return ret- 考虑判断节点 x 是否为 p、q 的最近祖先需要哪些信息：
- 文字描述太繁琐，直接看代码，非常清晰；
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
from dataclasses import dataclass
@dataclass
class Info: # 判断当前节点是否为答案需要从子节点了解到的信息
has_p: bool
has_q: bool
ret: TreeNode
def dfs(x):
if not x: return Info(False, False, None)
# l, r = dfs(x.left), dfs(x.right)
# 提前结束
l = dfs(x.left)
if l.ret: return l
r = dfs(x.right)
if r.ret: return r
has_p = x.val == p.val or l.has_p or r.has_p
has_q = x.val == q.val or l.has_q or r.has_q
ret = None
if has_p and has_q:
ret = l.ret if r.ret is None else r.ret # 左右子节点
ret = x if ret is None else ret # x 节点才是
return Info(has_p, has_q, ret)
return dfs(root).ret
给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
输出描述：分别输出是否为搜索二叉树、完全二叉树。- 判断二叉搜索树的条件：
- 当前节点的值大于左树的最大值，小于右树的最小值，且左右子树都是二叉搜索树；
- 判断完全二叉树的条件：
- 左右子树都是满二叉树，且高度相同（满二叉树）；
- 左右子树都是满二叉树，且左子树的高度+1；
- 左子树是满二叉树，右子树是完全二叉树，且高度相同；
- 左子树是完全二叉树，右子树是满二叉树，且左子树的高度+1；
- 综上：
- 我们需要存储信息有：最大值、最小值、高度、是否二叉搜索树、是否满二叉树、是否完全二叉树；
- 对空节点，初始化为：无穷小、无穷大、0、是、是、是；
- 详见代码；
Python
class Solution:
def judgeIt(self , root: TreeNode) -> List[bool]:
from dataclasses import dataclass
@dataclass
class Info:
mx: int # 整棵树的最大值
mi: int # 整棵树的最小值
height: int # 树的高度
is_bst: bool # 是否搜索二叉树
is_full: bool # 是否满二叉树
is_cbt: bool # 是否完全二叉树
def dfs(x):
if not x: return Info(float('-inf'), float('inf'), 0, True, True, True)
l, r = dfs(x.left), dfs(x.right)
# 使用左右子树的信息得到当前节点的信息
mx = max(x.val, r.mx)
mi = min(x.val, l.mi)
height = max(l.height, r.height) + 1
is_bst = l.is_bst and r.is_bst and l.mx < x.val < r.mi
is_full = l.is_full and r.is_full and l.height == r.height
is_cbt = is_full or \
l.is_full and r.is_full and l.height - 1 == r.height or \
l.is_full and r.is_cbt and l.height == r.height or \
l.is_cbt and r.is_full and l.height - 1 == r.height
return Info(mx, mi, height, is_bst, is_full, is_cbt)
info = dfs(root)
return info.is_bst, info.is_cbt