写在前
本部分题目，讨论自顶向下的情况，就是从某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束，而继续细分的话还可以分成一般路径与给定和的路径。
注意：这类题通常用深度优先搜索(DFS)和广度优先搜索(BFS)解决，BFS较DFS繁琐，这里为了简洁只展现DFS代码
1.二叉树的所有路径（257-易）
题目描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。
示例：
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
思路：递归实现
- 如果root不为空，我们才进行拼接！
- 判断是否到达叶子节点。如果到达，加入集合返回结果；否则，拼接箭头，递归左右子树。
代码实现：
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<>();
if (root == null) {
return ans;
}
dfs(root, "", ans);
return ans;
}
private void dfs(TreeNode root, String path, List<String> ans) {
if (root == null) {
return;
}
StringBuilder sb = new StringBuilder(path);
sb.append(String.valueOf(root.val));
if (root.left == null && root.right == null) {
ans.add(sb.toString());
} else {
sb.append("->");
dfs(root.left, sb.toString(), ans);
dfs(root.right, sb.toString(), ans);
}
}
2.求和路径（面试题04.12）
题目描述：给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例：
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:3
解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
思路：递归实现
- 本题关键是路径的起止点不确定，所以我们要在主函数递归左右子节点（累加结果）
- 我们维护一个变量记录结果，即当root.val == sum时我们获得一个结果，累积左右子节点。
代码实现：
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int dfs(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ans = sum == root.val ? 1 : 0;
sum -= root.val;
return dfs(root.left, sum) + dfs(root.right, sum) + ans;
}
3.路径总和（112-易）
题目描述：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
思路：递归实现
- 终止条件，如果当前节点为空，返回false
- 到达叶子节点，且sum = root.val
- 递归的左右子节点（注意更新sum值，即减去root.val）
代码实现：
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
sum -= root.val;
if (root.left == null && root.right == null && sum == 0) {
return true;
}
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
4.路径总和II（113-中）
题目描述：本题在上题基础上（从根节点到叶子节点的路径和等于给定值），要求找出这些路径！
示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
思路：递归实现，注意本题与257不同的是需要回溯。
- 我们先加入路径，不满足需要从队列中删除，所以需要实现一个双端队列。
- 注意找到一个结果也需要继续进行回溯。
代码实现：
List<List<Integer>> ans = new LinkedList<>();
Deque<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return ans;
}
dfs(root, targetSum);
return ans;
}
public void dfs(TreeNode root, int targetSum) {
if (root == null) {
return;
}
path.offerLast(root.val);
targetSum -= root.val;
if (root.left == null && root.right == null && targetSum == 0) {
ans.add(new LinkedList<>(path));
}
dfs(root.left, targetSum);
dfs(root.right, targetSum);
path.pollLast();
}
拓展（T437）：这里路径不限制从根节点到叶子节点，但是方向一定是从上到下的。
- 注意：区分开始节点（主递归函数）和结束节点（判断结束标志）！
代码实现：
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ans = 0;
sum -= root.val;
if (sum == 0) {
ans++;
}
ans += pathSumStartWithRoot(root.left, sum) + pathSumStartWithRoot(root.right, sum);
return ans;
}
5.从叶子节点开始的最小字符串（988-中）
题目描述：给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）
示例：
输入：[0,1,2,3,4,3,4]
输出："dba"
思路：递归实现，需要进行回溯，一些必要的函数：
- 直接使用StringBuilder的reverse()方法进行反转，反转两次是为了继续进行拼接。
- 使用compareTo()比较两个字符串的字典序（本质是比较ascii值）
- 使用deleteCharAt(待删除的索引)进行回溯
注意：我们是更新获取最小的字典序，所以我们初始值应该大于'z'的ascii值
代码实现：
String ans = "~";
public String smallestFromLeaf(TreeNode root) {
if (root == null) {
return ans;
}
dfs(root, new StringBuilder());
return ans;
}
private void dfs(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
sb.append((char)(root.val + 'a'));
if (root.left == null && root.right == null) {
sb.reverse();
String tmp = sb.toString();
sb.reverse();
if (tmp.compareTo(ans) < 0) {
ans = tmp;
}
}
dfs(root.left, sb);
dfs(root.right, sb);
sb.deleteCharAt(sb.length() - 1);
}
6.根节点到叶子节点数字之和（129-中）
题目描述：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的 所有数字之和 。
示例：
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
思路：递归实现，递归所有的路径（根节点到叶子节点），进行累加。
- 定义一个变量记录自上向下的路径和。
- 当到达叶子节点，找到一条路径和。
- 递归的寻找左右子节点。
代码实现：
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int pathSum) {
if (root == null) {
return 0;
}
pathSum = pathSum * 10 + root.val;
if (root.left == null && root.right == null) {
return pathSum;
}
return dfs(root.left, pathSum) + dfs(root.right, pathSum);
}
注意点
-
如果是找路径和等于给定target的路径的，那么可以不用新增一个临时变量cursum来判断当前路径和， 只需要用给定和target减去节点值，最终结束条件判断target==0即可。
-
是否要回溯：二叉树的问题大部分是不需要回溯的，原因如下：二叉树的递归部分：dfs(root->left),dfs(root->right)已经把可能的路径穷尽了,因此到任意叶节点的路径只可能有一条，绝对不可能出现另外的路径也到这个满足条件的叶节点的;但是对路径有限制，则需要使用回溯！如T4和T5；
二维数组(例如迷宫问题)的DFS,for循环向四个方向查找每次只能朝向一个方向，并没有穷尽路径， 因此某一个满足条件的点可能是有多条路径到该点的；
并且visited数组标记已经走过的路径是会受到另外路径是否访问的影响，这时候必须回溯
-
找到路径后是否要return:取决于题目是否要求找到叶节点满足条件的路径,如果必须到叶节点,那么就要return（也可以不return）; 但如果是到任意节点都可以，那么必不能return,因为这条路径下面还可能有更深的路径满足条件，还要在此基础上继续递归
-
是否要双重递归(即调用根节点的dfs函数后，继续调用根左右节点的pathsum函数)：看题目要不要求从根节点开始的，还是从任意节点开始
本部分题目，非自顶向下：就是从任意节点到任意节点的路径，不需要自顶向下
7.二叉树最大路径和（124-难）
题目描述：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
思路：递归实现，递归函数的关键写好递归处理的逻辑，怎么处理当前子树，需要返回什么，设置递归出口。关键是正确定义递归函数。
- 递归函数：计算当前节点为父亲节点提供的贡献（即当前节点到根节点的最大路径）。
- 递归的计算左右子节点的最大贡献值，逻辑：贡献值大于0，才会选取对应的节点最大贡献值
- 更新最大路径和（当前节点值和左右子节点最大贡献值）
特别注意：dfs函数中定义的是一个节点能贡献的最大值（计算该节点到根节点的最大路径），而我们统计结果时更新的二叉树中任意两点的最大路径（可能是多个节点到这个根节点的组合）！
代码实现：
private int ans = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
int left = root.left != null && root.val == root.left.val ? l : 0;
int right = root.right != null && root.val == root.right.val ? r : 0;
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
8.最长同值路径（687-中）
题目描述：给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例：
5
/ \
4 5
/ \ \
1 1 5
返回 2
思路：递归实现，思想与上题基本相似。
- 递归函数：当前节点到根节点的最长同值路径
- 递归左右子树的最长同值路径；逻辑：出现同值，更新路径左右路径，否则为0
- 更新最长同值路径
代码实现：
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int dfs(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ans = sum == root.val ? 1 : 0;
sum -= root.val;
return dfs(root.left, sum) + dfs(root.right, sum) + ans;
}
9.二叉树的直径（543-易）
题目描述：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例：
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思路：递归实现，递归实现，思想与上题基本相似，还是区分递归函数和最终结果的区别。
代码实现：
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
附（特殊）:所有距离为k的节点（863-中）
题目描述：给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
示例：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1
思路：本题搜索的大体思路可以按照图的bfs，我们需要给所有节点添加一个指向父节点的引用（这样就知道了距离该节点1距离的所有节点），进而找到距离target节点为k的所有节点。
- 用map集合构建每个节点的父节点，即建立当前节点到父节点的引用（构建图）
- 用hashset记录节点是否被访问过
- 我们可以看成以当前节点为中心的辐射（是一种广度搜索的思想），完成一层之后k--。
代码实现：
private Map<TreeNode, TreeNode> parents;
private Set<TreeNode> isVisited;
private List<Integer> ans;
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
parents = new HashMap<>();
getParents(root, null);
isVisited = new HashSet<>();
ans = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
queue.add(target);
while (!queue.isEmpty()) {
if (k-- == 0) {
while (!queue.isEmpty()) {
ans.add(queue.poll().val);
}
break;
}
int size = queue.size();
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
isVisited.add(node);
if (node.left != null && !isVisited.contains(node.left)) {
queue.add(node.left);
}
if (node.right != null && !isVisited.contains(node.right)) {
queue.add(node.right);
}
TreeNode p = parents.get(node);
if (p != null && !isVisited.contains(p)) {
queue.add(p);
}
}
}
return ans;
}
private void getParents(TreeNode root, TreeNode parent) {
if (root == null) {
return;
}
parents.put(root, parent);
getParents(root.left, root);
getParents(root.right, root);
}
注意点
- left,right代表的含义要根据题目所求设置，比如最长路径、最大路径和等等
- 全局变量res的初值设置是0还是INT_MIN要看题目节点是否存在负值,如果存在就用INT_MIN，否则就是0
- 注意两点之间路径为1，因此一个点是不能构成路径的
巨人的肩膀：
网友评论