写在前
本部分题目，讨论自顶向下的情况，就是从某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束，而继续细分的话还可以分成一般路径与给定和的路径。
注意：这类题通常用深度优先搜索(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，因此一个点是不能构成路径的
