【LeetCode】437. 路径总和 III

红太狼 2023-06-01 11:12 20阅读 0赞

## [437. 路径总和 III][437. _ III] ##

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

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

二叉树不超过1000个节点，且节点数值范围是 \[-1000000,1000000\] 的整数。

示例：

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

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

返回 3。和等于 8 的路径有:

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

--------------------

## 双重递归 ##

/* 思路： 1.dfs是求从根节点出发到叶子节点满足条件的路径总数 2.将给定的二叉树看成三个部分：根节点、左子树、右子树 3.三部分可以看成一个递归结构，先求从根节点出发满足条件的路径总数(dfs(root))， 再递归求左子树(pathSum(root.left))，递归求右子树(pathSum(root.right)) 总结： 1.双重递归，从全局找外层递归(如思路中的三个部分)，再从部分中找内层递归(如思路中的dfs) */ class Solution { private int count = 0; //存放结果 public int pathSum(TreeNode root, int sum) { if(root == null) return 0; dfs(root, sum); //求从根节点出发满足条件的路径总数 pathSum(root.left, sum); //递归求左子树 pathSum(root.right, sum); //递归求右子树 return count; } private void dfs(TreeNode root, int sum){ if(root == null) return; sum -= root.val; if(sum == 0) count++; //满足条件结果加一 dfs(root.left, sum); //继续往左子树找 dfs(root.right, sum); //继续往右子树找 } }

## 单重递归 ##

/* 思路： 1.用双重递归会重复计算很多次，其实我们只用单递归就可以解决， 不妨将已经走过的路径值保存到book数组 2.到i节点，就可以根据book倒序遍历，找到从i节点到根节点满足条件的路径总数 3.递归到最底层也就是叶子节点时，找出叶子节点到根节点的满足条件的路径总数之后， 需要将book数组回溯到上一层的状态，以便从上一层继续寻找 总结： 1.将已经求出的值保存，当下次递归时可以直接使用， 省去了重复计算浪费的时间，相当于用空间换取时间 2.递归返回到上层时，我们有时需要原来上层递归的状态，这时就需要用到回溯 */ class Solution { private int count = 0; //存放结果 public int pathSum(TreeNode root, int sum) { dfs(root, sum, new ArrayList<Integer>()); return count; } private void dfs(TreeNode root, int sum, ArrayList<Integer> book){ if(root == null) return; book.add(root.val); //加入当前节点的值 int cur_sum = 0; for(int i = book.size() - 1; i >= 0; i--){ //从当前节点往根节点寻找满足条件的路径总数 cur_sum += book.get(i); if(cur_sum == sum) count++; } dfs(root.left, sum, book); //递归求左子树 dfs(root.right, sum, book); //递归求右子树 book.remove(book.size() - 1); //回溯到上一次的状态，以便继续寻找 } }

转载于:https://www.cnblogs.com/huowuyan/p/11442057.html

[437. _ III]: https://leetcode-cn.com/problems/path-sum-iii/