专栏首页米扑专栏【leetcode】Path Sum

【leetcode】Path Sum

Question:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Anwser 1:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL){
            return false;
        }
        
        int sub = sum - root->val;
        if(sub == 0 && root->left == NULL && root->right == NULL){
            return true;
        }
        
        bool left = hasPathSum(root->left, sub);
        bool right = hasPathSum(root->right, sub);
        
        return left || right;
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Populating Next Right Pointers in Each Node II

    Follow up for problem "Populating Next Right Pointers in Each Node".

    阳光岛主
  • 【leetcode】Populating Next Right Pointers in Each Node

    Populate each next pointer to point to its next right node. If there is no next ...

    阳光岛主
  • 【leetcode】Sum Root to Leaf Numbers

    Given a binary tree containing digits from 0-9 only, each root-to-leaf path coul...

    阳光岛主
  • centos7下安装Python的pip

    root用户使用yum install -y python-pip 时会报如下错误:

    py3study
  • linux centos中添加删除修改环境变量,设置java环境变量

    前言 安装完软件必要添加环境变量。指令很少,然而长时间不写就会不自信:我写的对吗?于是百度开始,于是发现又是各有千秋。好吧,好记星不如烂笔头。当然,最重要的是,...

    Ryan-Miao
  • 恭喜你成为腾讯云锦鲤

           重磅! ? 9月11号,我们「DNSPod十问」栏目 将邀请到一位特殊嘉宾!  同时,为了庆祝腾讯云十周年 预祝腾讯云数字生态大会的举办 我们将...

    腾讯云DNSPod团队
  • Leetcode 203 Remove Linked List Elements

    Remove all elements from a linked list of integers that have value val. Exampl...

    triplebee
  • Leetcode 101. Symmetric Tree

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 数据分析篇 | 如何安装 Python 数据分析编程环境

    呆鸟发现一些新手用什么 IDE 的都有,IDLE、Spyder、PyCharm、VSCode、Jupyter 等等,本文不想探究哪种 IDE 更好,只想说,初学...

    叫我龙总
  • eclipse/che 命令 -ubuntu

    访问che的webide,点击左侧stacks,在右侧的列表中选择自己需要的运行时环境点进进入详情界面

    Meet相识

扫码关注云+社区

领取腾讯云代金券