LeetCode.437.Path Sum III 二叉树的路径和3

题目描述

437 Path Sum III
https://leetcode-cn.com/problems/path-sum-iii/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

---

解题过程

递归先序遍历二叉树，每次计算以当前节点为路径终点的所有路径和。
用一个数组保存从根节点到当前节点路径，这是二叉树问题中非常常用的一个方法。
遍历二叉树时间复杂度 O(n), 每次遍历需要计算路径和O(logn), 所以总的时间复杂度是O(nlogn)

public int pathSum(TreeNode root, int sum) {
    return pathSum(root, new ArrayList<>(), sum);
}

// 在二叉树root中寻找和为sum的路径，parent 是父节点, 返回结果个数
private int pathSum(TreeNode root, List<Integer> parent, int sum) {
    if (null == root) {
        return 0;
    }
    // 结果个数
    int count = 0;
    parent.add(root.val);
    StringBuilder path = new StringBuilder();
    int pathSum = 0;
    // 从当前节点往上倒序求累加和，比较是否为sum
    for (int i = parent.size() - 1; i >= 0; i--) {
        pathSum += parent.get(i);
        path.insert(0, parent.get(i) + "->");
        if (pathSum == sum) {
            count += 1;
            // 提交的代码中不能往控制台打印，否则超时间限制
//                    System.out.println(path.toString());
        }
    }
    if (null != root.left) {
        count += pathSum(root.left, parent, sum);
    }
    if (null != root.right) {
        count += pathSum(root.right, parent, sum);
    }
    // 递归完左右子树要去掉parent中的当前节点
    parent.remove(parent.size() - 1);
    return count;
}

---

GitHub代码

algorithms/leetcode/leetcode/_437_PathSum3.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_437_PathSum3.java

---