leetcode 437题

leetcode 437 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例1

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例2

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

二叉树的节点个数的范围是 [0,1000]
109 <= Node.val <= 109
1000 <= targetSum <= 1000

思路

有2中情况

如果包含根节点，那么就在它的左子树和右子树仲寻找和为 sum - root.val 的情况
不包含该 root 节点，那么就需要在它的左子树和右子树仲分别寻找和为 sum 的节点

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */

function pathSum(root, sum) {
    if (root === null) {
        return 0;
    }
    let res = findPath(root, sum);
    res += pathSum(root.left, sum);
    res += pathSum(root.right, sum);
    return res;
}

function findPath(root, sum) {
    if (root === null) {
        return 0;
    }
    let res = 0;
    if (root.val === sum) {
        res++;
    }
    res += findPath(root.left, sum - root.val);
    res += findPath(root.right, sum - root.val);
    return res;
}

复杂度分析:

时间复杂度: O(N^2)
空间复杂度：O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG 科学上网工具

leetcode 437 路径总和 III

思路

代码

CATALOG

FEATURED TAGS

FRIENDS