【LeetCode刷题日记】112.递归中的「减法思维」：一题带你打通二叉树路径求和的任督二脉

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰来到了我们每日的刷题环节由于接近期末周每天自己学习的时间就变得少了但还是要坚持每天学一点到了暑假再猛学两个月想想还有点期待。摘要二叉树路径求和问题是一道经典的递归入门题看似简单却暗含递归思维的底层逻辑。本文以 LeetCode 112 题「路径总和」为例深入剖析两种核心解法递归与迭代。重点阐释递归中「递减目标值」的巧妙之处——通过将路径和问题转化为剩余值问题实现了无状态传递的优雅递归。文章详细拆解了递归函数的执行流程解答了初学者常见的困惑为什么找到答案后还要逐层返回同时提供栈实现的三种迭代写法并对比两者的适用场景。通过本文你将真正理解递归的本质——递是深入探索归是逐层反馈。题目背景给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和targetSum。如果存在返回true否则返回false。叶子节点是指没有子节点的节点。示例 1输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22输出true解释等于目标和的根节点到叶节点路径如上图所示。示例 2输入root [1,2,3], targetSum 5输出false解释树中存在两条根节点到叶子节点的路径 (1 -- 2): 和为 3 (1 -- 3): 和为 4 不存在 sum 5 的根节点到叶子节点的路径。示例 3输入root [], targetSum 0输出false解释由于树是空的所以不存在根节点到叶子节点的路径。题目解析我们刚拿到这个题目可以联想到我们之前做过的一道题二叉树的所有路径在那里我们初步认识了回溯并具体实现得到了二叉树的所有路径而我们这题仅仅是要找到某一条或者几条的路径把这条路径的总和加起来看看是否等于我们的目标值路径是从根节点到叶子节点所谓的叶子节点就是没有左右子节点的节点。还有关键的一步就是我们怎么拿到一整条路径上的所有节点的和呢我们传入的是我们的目标值我们在递归的时候每一次递归都能得到当前的节点值那我们就可以拿目标值减去节点值如果最后目标值变成了0那么这条路径就是符合的。ps当然累加也是可以的但是需要额外维护一个状态也就是当前路径的节点值的和。具体的代码实现最直观的方法是深度优先搜索DFS从根节点向下递归遍历每经过一个节点就减去其值到达叶子节点时判断剩余和是否为 0。递归终止条件当前节点为空 → 返回false当前节点是叶子节点无左右孩子→ 返回节点值 targetSum否则递归检查左右子树目标值减去当前节点值java if (root.left null root.right null) { return root.val targetSum; // 叶子节点判断当前值是否等于剩余目标值 }这行代码的意思是如果当前节点是叶子节点判断root.val是否等于targetSum如果相等返回true如果不相等返回false逻辑运算符||的含义java return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);这个||是逻辑或运算符特点短路特性如果左边返回true右边就不会执行只要有一条路径成功整个表达式就为true等价于java // 写法1用 || 简洁版 return dfs(left, newTarget) || dfs(right, newTarget); // 写法2展开后的等价代码 boolean leftResult hasPathSum(root.left, targetSum - root.val); if (leftResult) return true; // 左边找到了就不用查右边 boolean rightResult hasPathSum(root.right, targetSum - root.val); return rightResult;直观理解这句话可以翻译成当前节点到叶子节点的路径和是否能等于targetSum等于问①左子树中能否找到一条路径其和等于targetSum - 当前节点值②右子树中能否找到一条路径其和等于targetSum - 当前节点值只要①或②有一个成立答案就是true递归找到答案后不会瞬间传送回起点而是沿着调用链原路返回每层都执行一次return就像爬梯子一样一级一级退出来。这就是为什么虽然结果在很深的节点就确定了但程序还要执行那么多return的原因——它在清理调用栈把控制权逐级交还给上层。代码实现java class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { // 节点为空没有路径 if (root null) { return false; } // 到达叶子节点判断当前值是否等于剩余目标值 if (root.left null root.right null) { return root.val targetSum; } // 递归左右子树目标值减去当前节点值 return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } }我们这里也可以使用迭代法用栈来实现。具体逻辑其实还是一样的不过我们可以用一个栈或者两个栈来实现我们入栈的顺序也要考虑好要右孩子先入栈栈是后进先出我们要先处理左孩子。方法一同时存储节点和当前和最直观java class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root null) { return false; } // 栈中存储节点, 从根到该节点的路径和 StackPairTreeNode, Integer stack new Stack(); stack.push(new Pair(root, root.val)); while (!stack.isEmpty()) { PairTreeNode, Integer pair stack.pop(); TreeNode node pair.getKey(); int currentSum pair.getValue(); // 到达叶子节点检查路径和是否等于目标值 if (node.left null node.right null) { if (currentSum targetSum) { return true; } } // 右孩子先入栈因为栈是后进先出左孩子会先处理 if (node.right ! null) { stack.push(new Pair(node.right, currentSum node.right.val)); } if (node.left ! null) { stack.push(new Pair(node.left, currentSum node.left.val)); } } return false; } }方法二使用两个栈更清晰java class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root null) { return false; } // 节点栈和对应的路径和栈 StackTreeNode nodeStack new Stack(); StackInteger sumStack new Stack(); nodeStack.push(root); sumStack.push(root.val); while (!nodeStack.isEmpty()) { TreeNode node nodeStack.pop(); int currentSum sumStack.pop(); // 检查叶子节点 if (node.left null node.right null) { if (currentSum targetSum) { return true; } } // 右孩子先入栈 if (node.right ! null) { nodeStack.push(node.right); sumStack.push(currentSum node.right.val); } if (node.left ! null) { nodeStack.push(node.left); sumStack.push(currentSum node.left.val); } } return false; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励