二叉树路径题的DFS模版

1.力扣题543. 二叉树的直径687. 最长同值路径1372. 二叉树中的最长交错路径124. 二叉树中的最大路径和1373. 二叉搜索子树的最大键值和2.模板class Solution { private int max Integer.MIN_VALUE; // 全局最大答案 public int XXX(TreeNode root) { // 主函数 dfs(root); return max; } private int dfs(TreeNode node) { // 后序DFS if (node null) return 0; // 或根据题意返回负无穷 int left dfs(node.left); // 左子树返回“从左子节点出发的最大路径” int right dfs(node.right); // 右子树返回“从右子节点出发的最大路径” // 【关键】在这里计算“经过当前节点”的局部最优路径更新全局max // 不同题目的计算方式不同但模板一样 // 返回给父节点的值通常是“从当前节点出发向下的最大路径” return Math.max(left, right) node.val; // 根据题目调整 } }3.多个返回值1. LeetCode 1372. 二叉树中的最长交错路径核心思路超级重要先背下来 这题不是后序返回两个值那么简单而是用 top-down DFS 方向标记最清晰。 我们从根节点开始分别尝试“第一次往左走”和“第一次往右走”。 dfs(node, len, isLeft) 的含义 len当前已经走过的边数答案就是边数不是节点数 isLeft上一步是往左走的true 上一步走了左孩子 如果 isLeft true那么继续交错就必须走右孩子len1同时也可以从左孩子重新开始新路径len1。class Solution { private int maxLen 0; ​ public int longestZigZag(TreeNode root) { if (root null) return 0; // 从根节点出发分别尝试第一次向左走和第一次向右走 dfs(root.left, 1, true); // 上一步“向左走”到达左孩子 dfs(root.right, 1, false); // 上一步“向右走”到达右孩子 return maxLen; } ​ /** * dfs(node, len, isLeft) * len 当前路径已经走的边数 * isLeft true 表示到达当前node的上一步是“向左走”的 */ private void dfs(TreeNode node, int len, boolean isLeft) { if (node null) return; ​ maxLen Math.max(maxLen, len); // 更新全局最长边数 ​ if (isLeft) { // 继续交错上一步是左 → 这一步必须走右 dfs(node.right, len 1, false); // 也可以从左孩子重新开始一条新路径长度1 dfs(node.left, 1, true); } else { // 继续交错上一步是右 → 这一步必须走左 dfs(node.left, len 1, true); // 也可以从右孩子重新开始一条新路径长度1 dfs(node.right, 1, false); } } }没有返回值是因为返回值len已经通过传参的方式返回了可以直接进行max的更新2. LeetCode 1373. 二叉搜索树中的最大子树和Hard中最经典的一题核心思路这题要同时判断是否是BST 计算子树和 记录子树最小/最大值用来判断父节点是否BST。所以dfs必须返回4个信息我们用一个长度为4的数组res[0] 是否是BST1是0不是res[1] 子树总和res[2] 子树最小值res[3] 子树最大值全局max只在“是BST”时更新子树和。class Solution { private long maxSum 0; // 全局最大BST子树和用long防止溢出 ​ public int maxSumBST(TreeNode root) { if (root null) return 0; dfs(root); return (int) maxSum; } ​ /** * dfs 返回一个长度为4的数组 * res[0] 是否是BST (1是, 0不是) * res[1] 子树总和 * res[2] 子树最小值 * res[3] 子树最大值 */ private long[] dfs(TreeNode node) { if (node null) { // 空节点是BST总和0最小值∞最大值-∞ return new long[] {1, 0, Long.MAX_VALUE, Long.MIN_VALUE}; } ​ long[] left dfs(node.left); long[] right dfs(node.right); ​ // 判断当前子树是否是BST boolean isBST (left[0] 1) (right[0] 1) node.val left[3] node.val right[2]; ​ if (isBST) { long sum left[1] right[1] node.val; maxSum Math.max(maxSum, sum); // 更新全局最大和 ​ // 返回给父节点 long minVal Math.min(node.val, left[2]); long maxVal Math.max(node.val, right[3]); return new long[] {1, sum, minVal, maxVal}; } else { // 不是BST只返回不是BST的状态sum/min/max不用管父节点不会用 return new long[] {0, 0, 0, 0}; } } }为什么返回值要4个isBST告诉父节点“我这棵子树合不合法”sum如果是BST就把和传上去min和max让父节点能判断“我比左子树最大值大、比右子树最小值小” 这四个信息缺一不可这就是1373最难的地方。