OMG OMG OMG OMG！！！自闭了，又遇到了一个很烦很烦很烦类型的题目
可以先去看文章 二叉树--纲领篇，熟悉二叉树的核心要义！前文介绍过树相关题目所用到的方法无非两种「分解子问题」&&「遍历」，详情可见 二叉树「遍历」And「分解」
同时也可以去看看本人总结的一篇关于二叉搜索树经典题目的文章，里面详细的分析了用递归解决问题时需要明确的要素，详情可见 二叉搜索树(BST)
接下来先梳理一下路径相关题目的形式
详情可见题目 路径总和
这个题目很简单，没什么好说的，直接看代码
// 分解子问题public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null && root.val == targetSum) return true; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}详情可见题目 路径总和 II
这个题目有点意思，「分解子问题 && 遍历」都可以写出来，只不过两个方法的麻烦程度简直不能比！！！
本题和这个里面的「二叉树所有路径」很像，可以参考 传送门
x// 遍历// 一般遍历都需要借助全局变量private List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) { traversal(root, targetSum, new ArrayList<Integer>()); return res;}private void traversal(TreeNode root, int targetSum, List<Integer> list) { if (root == null) return ; list.add(root.val); if (root.left == null && root.right == null && root.val == targetSum) { res.add(new ArrayList<>(list)); } traversal(root.left, targetSum - root.val, list); traversal(root.right, targetSum - root.val, list); list.remove(list.size() - 1);}
// 分解子问题public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; List<Integer> list = new ArrayList<>(); list.add(root.val); if (root.left == null && root.right == null && root.val == targetSum) { res.add(new ArrayList<>(list)); return res; } List<List<Integer>> leftRes = pathSum(root.left, targetSum - root.val); List<List<Integer>> rightRes = pathSum(root.right, targetSum - root.val); if (leftRes.size() != 0) { for (List<Integer> left : leftRes) { List<Integer> cur = new ArrayList<>(list); cur.addAll(left); res.add(cur); } } if (rightRes.size() != 0) { for (List<Integer> right : rightRes) { List<Integer> cur = new ArrayList<>(list); cur.addAll(right); res.add(cur); } } return res;}详情可见题目 路径总和 III
这个题目需要用到「前缀和」的思想，详情可见 前缀和技巧
xxxxxxxxxxprivate Map<Integer, Integer> preSumCount = new HashMap<>();private int pathSum;private int targetSum;private int res;public int pathSum(TreeNode root, int targetSum) { if (root == null) return 0; this.pathSum = 0; this.targetSum = targetSum; this.res = 0; // base case preSumCount.put(0, 1); traversal(root); return res;}private void traversal(TreeNode root) { if (root == null) return ; // 先序位置：首次进入时执行 pathSum += root.val; res += preSumCount.getOrDefault(pathSum - targetSum, 0); preSumCount.put(pathSum, preSumCount.getOrDefault(pathSum, 0) + 1);
traversal(root.left); traversal(root.right); // 后序位置：即将离开时的执行 preSumCount.put(pathSum, preSumCount.get(pathSum) - 1); pathSum -= root.val;}详情可见题目 从叶结点开始的最小字符串
其实这个题目就是遍历出所有路径，然后比较路径的大小
只不过比较的时候有点麻烦，涉及到了字符串的比较
xxxxxxxxxx// 遍历// 借助全局遍历// 存放结果private String res = new String();// 中间路径private StringBuffer sb = new StringBuffer();public String smallestFromLeaf(TreeNode root) { traversal(root); return res;}private void traversal(TreeNode root) { if (root == null) return ; // 进入时加入当前元素 sb.append((char) (root.val + 'a')); // 判断是否为叶子节点 if (root.left == null && root.right == null) { // 比较过程 String s = new StringBuffer(sb).reverse().toString(); if ("".equals(res)) res = s; res = s.compareTo(res) <= 0 ? s : res; } traversal(root.left); traversal(root.right); // 离开时移除当前元素 sb.setLength(sb.length() - 1);}详情可见题目 二叉树的直径
思路：分解子问题，当前节点的直径和 = 左子树的高度 + 右子树的高度
技巧：利用后序遍历，刚好可以一边求高度，一边取最值；不然就需要一次次的重复求好多次高度
⚠️ 区分清楚 高度 && 深度
xxxxxxxxxxprivate int res = 0;public int diameterOfBinaryTree(TreeNode root) { diameterOfBinaryTreeHelper(root); return res;}private int diameterOfBinaryTreeHelper(TreeNode root) { if (root == null) return 0; int lh = diameterOfBinaryTreeHelper(root.left); int rh = diameterOfBinaryTreeHelper(root.right); // 后序遍历处理阶段 // 更新最值 res = Math.max(res, lh + rh); // 返回当前子树高度 return Math.max(lh, rh) + 1;}详情可见题目 二叉树中的最大路径和
这个题目难度是 hard，看起来吓一跳，但是本人一开始瞎摸索，居然写出来了，但是没有其他人的解法妙
xxxxxxxxxx// 本人解法 😭private int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) { maxPathSumHelper(root); return res;}private int maxPathSumHelper(TreeNode root) { if (root == null) return 0; int leftMax = maxPathSumHelper(root.left); int rightMax = maxPathSumHelper(root.right); // 主要利用下面四行代码进行了负值的舍弃 // 分别和加上左右，只加左或右，只有根 进行最大值取舍 // 其实效果和下面与 0 进行比较一样 res = Math.max(res, leftMax + rightMax + root.val); res = Math.max(res, leftMax + root.val); res = Math.max(res, rightMax + root.val); res = Math.max(res, root.val);
// 返回值也只要和根单独进行一个比较 return Math.max(Math.max(leftMax, rightMax) + root.val, root.val);}
// 优质解法private int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) { maxPathSumHelper(root); return res;}private int maxPathSumHelper(TreeNode root) { if (root == null) return 0; // 核心地方：和 0 做一个取舍 // 如果是负值，则舍弃 // 这样就可以不需要从叶子节点开始到叶子节点结束 int leftMax = Math.max(0, maxPathSumHelper(root.left)); int rightMax = Math.max(0, maxPathSumHelper(root.right));
res = Math.max(res, leftMax + rightMax + root.val);
return Math.max(leftMax, rightMax) + root.val;}突然看到了一篇面经，有的面试官需要让你输出最长和的路径，下面来实现一下：
xxxxxxxxxxclass Solution { // 存储结果 // 一开始路径和需要初始为最小值 private Pair ans = new Pair(Integer.MIN_VALUE, new ArrayList<>()); public int maxPathSum(TreeNode root) { maxPathSumHelper(root); return ans.sum; }
private Pair maxPathSumHelper(TreeNode root) { Pair res = new Pair(0, new ArrayList<>()); if (root == null) return res; Pair leftRes = maxPathSumHelper(root.left); Pair rightRes = maxPathSumHelper(root.right); // 舍去路径和为负数的孩子 if (leftRes.sum <= 0) leftRes = new Pair(0, new ArrayList<>()); if (rightRes.sum <= 0) rightRes = new Pair(0, new ArrayList<>()); // 记录当前路径和，即：左孩子 根 右孩子 int curSum = root.val + leftRes.sum + rightRes.sum; // 更新最长路径和 if (ans.sum < curSum) { List<Integer> curPath = new ArrayList<>(); curPath.addAll(leftRes.path); curPath.add(root.val); curPath.addAll(rightRes.path); ans = new Pair(curSum, curPath); } // 处理返回值 // 从左右孩子中选择一条更长的路 if (leftRes.sum >= rightRes.sum) { res.path.addAll(leftRes.path); res.path.add(root.val); res.sum = root.val + leftRes.sum; } else { res.path.add(root.val); res.path.addAll(rightRes.path); res.sum = root.val + rightRes.sum; } return res; }}class Pair { // 存储路径和 int sum; // 存储路径 List<Integer> path; public Pair(int sum, List<Integer> path) { this.sum = sum; this.path = path; }}详情可见题目 最长同值路径
当时一瞅，不知道何从下手；直到看到了一句提醒，有了启发 返回和当前节点值相同的最大高度 说白了就是搞清楚递归三要素中返回值的含义
xxxxxxxxxx// 记录最终结果private int res = 0;public int longestUnivaluePath(TreeNode root) { longestUnivaluePathHelper(root); return res;}private int longestUnivaluePathHelper(TreeNode root) { if (root == null) return 0; int left = longestUnivaluePathHelper(root.left); int right = longestUnivaluePathHelper(root.right); // 后序遍历处理阶段 // maxLen：记录当前路径长度 int maxLen = 0; // maxSameDepth：记录当前最大高度 int maxSameDepth = 0; // 如果左孩子不为空，且值相同 if (root.left != null && root.val == root.left.val) { // maxLen 加上左孩子路径 maxLen += (left + 1); // 更新最大高度 maxSameDepth = Math.max(maxSameDepth, left + 1); } if (root.right != null && root.val == root.right.val) { // maxLen 加上右孩子路径 maxLen += (right + 1); // 更新最大高度 maxSameDepth = Math.max(maxSameDepth, right + 1); } // 更新最终结果 res = Math.max(res, maxLen); return maxSameDepth; }是不是感觉一下把正确代码给出，看似太简单了
直接上几个本人自闭时候的错误版本（核心代码部分）
xxxxxxxxxx// 错误版本 1int maxLen = 0;if (root.left != null && root.val == root.left.val) maxLen += (left + 1);if (root.right != null && root.val == root.right.val) maxLen += (right + 1);res = Math.max(res, maxLen);// 错误点：直接返回了路径的长度，会导致结果 大于 正确结果// 正确思路：返回和当前节点值相同的最大高度return curRes;
// --------------- 分隔线 ---------------
// 错误版本 2// 后序遍历处理阶段int maxLen = 0;if (root.left != null && root.val == root.left.val) maxLen += (left + 1);if (root.right != null && root.val == root.right.val) maxLen += (right + 1);res = Math.max(res, maxLen);// 错误点：没有考虑值相同这个因素，值不同的时候，也会返回 +1 的结果，会导致错误// 正确思路：只有当值相同的时候，才返回；值不同的时候应该返回 0return Math.max(left, right) + 1;详情可见题目 二叉树中的最长交错路径
这个题目很有意思，本人一开始想到的就是分解子问题，结果把自己绕来绕去 绕晕了 😭😭😭
下面是分解的解法，可惜超时 😭😭😭
不过可以体会一下这种思想，即：最优解可能不在当前节点
xxxxxxxxxxprivate int res = 0;public int longestZigZag(TreeNode root) { helper(root); return res;}// 对于当前节点，最优解可能出现在该节点向左孩子进行搜索，也可能出现在该节点向右孩子进行搜索// 同时，也可能最优解不在当前节点，而在左右节点中private void helper(TreeNode root) { if (root == null) return ; // 对于最优解就在当前节点上时 res = Math.max(res, Math.max(searchZigZag(root, 0), searchZigZag(root, 1))); // 如果不在，则继续搜索左右节点 helper(root.left); helper(root.right);}// 给定方向，进行搜索private int searchZigZag(TreeNode root, int dir) { if (root == null) return -1;
if (dir == 0) return searchZigZag(root.left, 1) + 1; else return searchZigZag(root.right, 0) + 1;}下面是进行了优化的解法，该解法很巧妙。利用一个数组，数组的第一个数表示当前节点向左搜索的结果，数组的第二个数表示当前节点向右搜索的结果
xxxxxxxxxxprivate int res = 0;public int longestZigZag(TreeNode root) { getPathSum(root); return res;}private int[] getPathSum(TreeNode root) { // 如果为空 -1 (此处也很妙) // 如果是叶子节点，则可以 +1 变成 0 // 如果是两个节点，则继续 +1 变成 1 // 刚好满足节点数量和边之间的关系 妙呀～～～ if (root == null) return new int[]{-1, -1}; int[] left = getPathSum(root.left); int[] right = getPathSum(root.right); // 后序遍历时处理 (发现很多题目都借助了后序遍历的特点) // 更新值，注意逻辑 int leftPath = left[1] + 1; int rightPath = right[0] + 1; res = Math.max(res, Math.max(leftPath, rightPath)); return new int[]{leftPath, rightPath};}详情可见题目 二叉树中的列表
这个题目也是变相的一种寻找路径，判断是否存在符合的路径
这个题目和上面的题目很像，如果利用「分解子问题」的思想去写更像
正确解可能是当前节点，也可能是孩子节点开始
xxxxxxxxxxpublic boolean isSubPath(ListNode head, TreeNode root) { if (head == null) return true; if (root == null) return false; // 三者满足其一就 🉑️ return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);}private boolean isSub(ListNode head, TreeNode root) { if (head == null) return true; if (root == null) return false; if (root.val != head.val) return false; return isSub(head.next, root.left) || isSub(head.next, root.right);}