树状图是一种在数学和计算机科学中常用的图形表示方法，它能够帮助我们直观地理解复杂的数据结构和算法。在解决树状图问题时，我们需要运用逻辑思维和数学技巧。以下将介绍二十道经典的树状图计算题，旨在帮助读者提升解决这类问题的能力。
1. 树的遍历
题目描述： 给定一棵树，请实现树的先序、中序和后序遍历算法。
解答思路：
- 先序遍历： 根节点 -> 左子树 -> 右子树
- 中序遍历： 左子树 -> 根节点 -> 右子树
- 后序遍历： 左子树 -> 右子树 -> 根节点
代码示例：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root):
if root:
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
2. 树的高度
题目描述： 给定一棵树，请计算树的高度。
解答思路：
- 树的高度定义为从根节点到最远叶子节点的最长路径上的节点数。
代码示例：
def tree_height(root):
if not root:
return 0
return 1 + max(tree_height(root.left), tree_height(root.right))
3. 树的直径
题目描述： 给定一棵树，请计算树的直径。
解答思路：
- 树的直径定义为树中任意两点间的最长路径长度。
代码示例：
def tree_diameter(root):
def helper(node):
if not node:
return 0, 0
left_height, left_diameter = helper(node.left)
right_height, right_diameter = helper(node.right)
return 1 + max(left_height, right_height), max(left_diameter, left_height + right_height)
return helper(root)[1]
4. 树的宽度
题目描述： 给定一棵树，请计算树的宽度。
解答思路：
- 树的宽度定义为树中任意一层节点数最多的层数。
代码示例：
from collections import deque
def tree_width(root):
if not root:
return 0
max_width = 0
queue = deque([root])
while queue:
level_width = len(queue)
max_width = max(max_width, level_width)
for _ in range(level_width):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return max_width
5. 树的层序遍历
题目描述： 给定一棵树，请实现树的层序遍历算法。
解答思路：
- 层序遍历按照从上到下、从左到右的顺序遍历树的所有节点。
代码示例：
from collections import deque
def level_order_traversal(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
6. 树的深度优先搜索（DFS）
题目描述： 给定一棵树，请实现树的深度优先搜索算法。
解答思路：
- 深度优先搜索按照从根节点到叶子节点的路径进行遍历。
代码示例：
def dfs(root):
if not root:
return
print(root.val, end=' ')
dfs(root.left)
dfs(root.right)
7. 树的广度优先搜索（BFS）
题目描述： 给定一棵树，请实现树的广度优先搜索算法。
解答思路：
- 广度优先搜索按照从根节点到叶子节点的层次进行遍历。
代码示例：
from collections import deque
def bfs(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
8. 树的路径和
题目描述： 给定一棵树和一个目标值，请找出所有从根节点到叶子节点的路径，使得路径上所有节点的值之和等于目标值。
解答思路：
- 使用深度优先搜索算法，从根节点开始遍历，将路径上的节点值累加，当累加值等于目标值时，记录路径。
代码示例：
def path_sum(root, target):
def dfs(node, path, target):
if not node:
return
path.append(node.val)
if not node.left and not node.right and sum(path) == target:
result.append(path.copy())
dfs(node.left, path, target)
dfs(node.right, path, target)
path.pop()
result = []
dfs(root, [], target)
return result
9. 树的节点层次
题目描述： 给定一棵树和一个节点值，请找出该节点所在的层次。
解答思路：
- 使用广度优先搜索算法，从根节点开始遍历，记录每个节点的层次，当找到目标节点时，返回其层次。
代码示例：
from collections import deque
def node_level(root, target):
if not root:
return -1
queue = deque([(root, 0)])
while queue:
node, level = queue.popleft()
if node.val == target:
return level
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
return -1
10. 树的节点距离
题目描述： 给定一棵树和两个节点值，请计算这两个节点之间的距离。
解答思路：
- 使用深度优先搜索算法，分别找到两个节点的父节点，然后沿着路径向上遍历，计算两个节点之间的距离。
代码示例：
def node_distance(root, u, v):
def find_ancestors(node, target, ancestors):
if not node:
return False
ancestors.append(node)
if node.val == target:
return True
if find_ancestors(node.left, target, ancestors) or find_ancestors(node.right, target, ancestors):
return True
ancestors.pop()
return False
ancestors_u = []
ancestors_v = []
find_ancestors(root, u, ancestors_u)
find_ancestors(root, v, ancestors_v)
distance = 0
while ancestors_u and ancestors_v:
ancestor_u = ancestors_u.pop()
ancestor_v = ancestors_v.pop()
if ancestor_u == ancestor_v:
distance += 2
else:
distance += 1
return distance
11. 树的节点层次和
题目描述： 给定一棵树和一个节点值，请计算该节点所在的层次的所有节点值之和。
解答思路：
- 使用深度优先搜索算法，从根节点开始遍历，记录每个节点的层次和值，当找到目标节点时，返回其层次和值之和。
代码示例：
def node_level_sum(root, target):
def dfs(node, level, path_sum):
if not node:
return 0
path_sum += node.val
if not node.left and not node.right and node.val == target:
return path_sum
return dfs(node.left, level + 1, path_sum) + dfs(node.right, level + 1, path_sum)
return dfs(root, 0, 0)
12. 树的节点路径和
题目描述： 给定一棵树和一个节点值，请找出所有从根节点到叶子节点的路径，使得路径上所有节点的值之和等于目标值。
解答思路：
- 使用深度优先搜索算法，从根节点开始遍历，将路径上的节点值累加，当累加值等于目标值时，记录路径。
代码示例：
def path_sum(root, target):
def dfs(node, path, target):
if not node:
return
path.append(node.val)
if not node.left and not node.right and sum(path) == target:
result.append(path.copy())
dfs(node.left, path, target)
dfs(node.right, path, target)
path.pop()
result = []
dfs(root, [], target)
return result
13. 树的节点度数
题目描述： 给定一棵树和一个节点值，请计算该节点的度数。
解答思路：
- 节点的度数定义为节点拥有的子节点数。
代码示例：
def node_degree(root, target):
def dfs(node, target):
if not node:
return 0
if node.val == target:
return node.left_count + node.right_count
return dfs(node.left, target) + dfs(node.right, target)
return dfs(root, target)
14. 树的节点连接
题目描述： 给定一棵树和一个节点值，请找到该节点的父节点。
解答思路：
- 使用深度优先搜索算法，从根节点开始遍历，记录每个节点的父节点，当找到目标节点时，返回其父节点。
代码示例：
def find_parent(root, target):
def dfs(node, parent):
if not node:
return None
if node.val == target:
return parent
left_parent = dfs(node.left, node)
if left_parent:
return left_parent
return dfs(node.right, node)
return dfs(root, None)
15. 树的节点兄弟
题目描述： 给定一棵树和一个节点值，请找到该节点的兄弟节点。
解答思路：
- 兄弟节点指的是在同一父节点下的相邻节点。
代码示例：
def find_sibling(root, target):
def dfs(node, target):
if not node:
return None
if node.val == target:
return node.left if node.left else node.right
left_sibling = dfs(node.left, target)
if left_sibling:
return left_sibling
return dfs(node.right, target)
return dfs(root, target)
16. 树的节点祖先
题目描述： 给定一棵树和一个节点值，请找到该节点的所有祖先节点。
解答思路：
- 祖先节点指的是从根节点到目标节点的路径上的所有节点。
代码示例：
def find_ancestors(root, target):
ancestors = []
def dfs(node, target):
if not node:
return False
if node.val == target:
ancestors.append(node)
return True
if dfs(node.left, target) or dfs(node.right, target):
ancestors.append(node)
return True
return False
dfs(root, target)
return ancestors
17. 树的节点子树
题目描述： 给定一棵树和一个节点值，请找到该节点的所有子树。
解答思路：
- 子树指的是以目标节点为根的子树。
代码示例：
def find_subtrees(root, target):
subtrees = []
def dfs(node, target):
if not node:
return
if node.val == target:
subtrees.append(node)
dfs(node.left, target)
dfs(node.right, target)
dfs(root, target)
return subtrees
18. 树的节点后代
题目描述： 给定一棵树和一个节点值，请找到该节点的所有后代节点。
解答思路：
- 后代节点指的是以目标节点为根的所有子节点。
代码示例：
def find_descendants(root, target):
descendants = []
def dfs(node, target):
if not node:
return
if node.val == target:
descendants.append(node)
dfs(node.left, target)
dfs(node.right, target)
dfs(root, target)
return descendants
19. 树的节点相邻节点
题目描述： 给定一棵树和一个节点值，请找到该节点的相邻节点。
解答思路：
- 相邻节点指的是在同一层且相邻的两个节点。
代码示例：
def find_adjacent(root, target):
adjacent = []
def dfs(node, target):
if not node:
return
if node.val == target:
if node.left:
adjacent.append(node.left)
if node.right:
adjacent.append(node.right)
dfs(node.left, target)
dfs(node.right, target)
dfs(root, target)
return adjacent
20. 树的节点最近公共祖先
题目描述： 给定一棵树和两个节点值，请找到这两个节点的最近公共祖先。
解答思路：
- 最近公共祖先指的是从根节点到这两个节点的路径上最近的公共节点。
代码示例：
def find_lowest_common_ancestor(root, u, v):
ancestors_u = set()
def find_ancestors(node, target, ancestors):
if not node:
return False
ancestors.add(node)
if node.val == target:
return True
if find_ancestors(node.left, target, ancestors) or find_ancestors(node.right, target, ancestors):
return True
ancestors.remove(node)
return False
find_ancestors(root, u, ancestors_u)
def dfs(node, target):
if not node:
return None
if node.val == target:
return node
left = dfs(node.left, target)
if left:
return left
return dfs(node.right, target)
ancestor_v = dfs(root, v)
while ancestor_v in ancestors_u:
ancestor_v = find_parent(root, ancestor_v)
return ancestor_v
通过以上二十道经典的树状图计算题，相信读者已经对树状图问题有了更深入的了解。在解决这些问题的过程中，读者可以锻炼自己的逻辑思维和编程能力。希望这些题目能够帮助读者在解决树状图问题时更加得心应手。