本文共 1252 字，大约阅读时间需要 4 分钟。

学习算法，锻炼自我！记录自己的成长过程！

问题描述：作为一名刚接触算法的开发者，你被要求编写一个函数，判断一棵二叉树是否存在一条从根节点到叶子节点的路径，这条路径上的所有节点值之和等于指定的目标值。

解决思路：对于这个问题，可以采用前序遍历（即深度优先搜索，DFS）的方式，利用栈来记录当前的路径和。每当访问一个节点时，我们将该节点的值加到栈顶的累加值上，然后将右节点和左节点按照一定规则推入栈中。具体来说，在每次弹出栈顶元素时，我们首先处理右节点，接着处理左节点。这样可以确保前序遍历的顺序。随着深入遍历，我们可以逐步计算路径和。当到达叶节点时，检查路径和是否等于目标值。如果在任何一步满足条件，则立即返回true。如果遍历完整个树都未找到符合条件的路径，则返回false。

代码实现：

function hasPathSum(root, targetSum) {
    if (!root) {
        return false; // 为空树则直接返回false
    }
    const stack = [ [root, root.val] ]; // 栈存储路径，其中每个元素包含节点和当前路径的累加和
    while (stack.length > 0) {
        const [currentNode, currentSum] = stack.pop(); // 弹出栈顶元素
        // 处理右子节点
        if (currentNode.right) {
            stack.push( [currentNode.right, currentSum + currentNode.right.val] );
        }
        // 处理左子节点
        if (currentNode.left) {
            stack.push( [currentNode.left, currentSum + currentNode.left.val] );
        }
        // 检查是否到达叶节点
        if (!currentNode.left && !currentNode.right) {
            // 如果到达叶节点且当前路径和等于目标值，返回true
            if (currentSum === targetSum) {
                return true;
            }
        }
    }
    // 全部遍历完毕未找到符合条件的路径
    return false;
}

这段代码通过栈结构实现了前序遍历，同时在访问每个节点时维护了当前路径的累加和。当到达叶节点时，检查和是否等于目标值。这种方法不仅时间复杂度为O(n)，空间复杂度也为O(h)，非常高效。

转载地址：http://dasgz.baihongyu.com/