专栏首页Michael阿明学习之路LeetCode 437. 路径总和 III(双重递归)

LeetCode 437. 路径总和 III(双重递归)

1. 题目

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

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

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

二叉树不超过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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/path-sum-iii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 以 root 开始求和
  • 以 root 的左右子节点开始求和
class Solution {
	int count = 0;
public:
    int pathSum(TreeNode* root, int sum) {
    	if(root == NULL)
    		return 0;
        pathSum(root->left,sum);//以root->left节点从新开始
        pathSum(root->right,sum);//以root->right节点从新开始
        add(root,sum,0);
        return count;
    }
    void add(TreeNode* root, int &sum, int cursum) 
    {
    	if(root == NULL)
    		return;
    	if(cursum+root->val == sum)
    		++count;
		add(root->left,sum,cursum+root->val);
		add(root->right,sum,cursum+root->val);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员面试金典 - 面试题 04.12. 求和路径(二叉树递归)

    注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。

    Michael阿明
  • LeetCode 156. 上下翻转二叉树(DFS)*

    给定一个二叉树,其中所有的右节点要么是具有兄弟节点(拥有相同父节点的左节点)的叶节点,要么为空 将此二叉树上下翻转并将它变成一棵树, 原来的右节点将转换成左叶...

    Michael阿明
  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • Mac 在命令行获得root权限

    这样就变成以root权限操作vim /etc/shells 这个命令,可以正常操作了。 

    week
  • 程序员面试金典 - 面试题 04.12. 求和路径(二叉树递归)

    注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。

    Michael阿明
  • Linux基础(day56)

    14.1 NFS介绍 NFS介绍 NFS是Network File System的缩写;这个文件系统是基于网路层面,通过网络层面实现数据同步 NFS最早...

    运维小白
  • LeetCode 146 LRU Cache

    实现一个缓存机制。很多人的写法都是使用HashTable, Map,Dictionary 或者别的工具。

    ShenduCC
  • LeetCode 156. 上下翻转二叉树(DFS)*

    给定一个二叉树,其中所有的右节点要么是具有兄弟节点(拥有相同父节点的左节点)的叶节点,要么为空 将此二叉树上下翻转并将它变成一棵树, 原来的右节点将转换成左叶...

    Michael阿明
  • 默认权限umask、文件系统权限、特殊权限

    第1章 权限相关错误 1.1 普通用户 ls /root/ /root  属于root 普通用户没有任何权限,所以无法查看 [oldboy@znix ~]$ l...

    惨绿少年
  • Golang Leetcode 226. Invert Binary Tree.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89043397

    anakinsun

扫码关注云+社区

领取腾讯云代金券