Skip to content

112. 路径总和 #36

Open
Open
@swiftwind0405

Description

@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

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions