112. 路径总和

[swiftwind0405]

方法一：深度优先遍历

解题思想：
在深度优先遍历的过程中，记录当前路径的节点值的和。
在叶子节点处，判断当前路径的节点值的和是否等于目标值。

代码：

var hasPathSum = function(root, sum) {
    if(!root) return false;
    let res = false;
    const dfs = (node, s) => {
        // console.log(node.val, s);
        // 如果是叶子节点，且当前路径的和为sum，就证明找到一个符合要求的路径
        if (!node.left && !node.right && s === sum) {
            res = true;
        }
        if(node.left) dfs(node.left, s + node.left.val);
        if(node.right) dfs(node.right, s + node.right.val);
    };
    dfs(root, root.val);
    return res;
};

复杂度分析：

• 时间复杂度：O(n)，遍历所有节点
• 空间复杂度：O(n)，递归堆栈的高度，也就是树的高度，最坏情况下是n（变成一个链表），在是完全平衡二叉树的前提下，则是logn