Path Sum

问:二叉树是否存在路径和等于sum的路径,若存在输出true,否则输出false 分析:递归调用二叉树,每次将上一层的val值传递给子结点并加上子节点的val,当传递到某个结点为叶子结点时,判断其val值是否等于sum 错点:二叉树为空,则无论sum为多少都为false,这个容易造成RE         二叉树只有根节点,则直接判断其值与sum的关系

class Solution
{
public:
    void PathSum(TreeNode *root,int val,int sum,int &flag)
    {
        root->val+=val;
        if(root->left==NULL && root->right==NULL && sum==root->val)
        {
            flag=1;
        }
        if(root->left) PathSum(root->left,root->val,sum,flag);
        if(root->right) PathSum(root->right,root->val,sum,flag);
    }
    bool hasPathSum(TreeNode *root, int sum)
    {
        if(root==NULL)
        {
            return false;
        }
        if(root->left==NULL && root->right==NULL)
        {
            if(root->val==sum) return true;
            return false;
        }
        int flag=0;
        if(root->left)  PathSum(root->left,root->val,sum,flag);
        if(root->right) PathSum(root->right,root->val,sum,flag);
        if(flag) return true;
        return false;
    }
};
class Solution
{
public:
    bool PathSum(TreeNode *root,int sum,int val)
    {
         if(root==NULL)  return false;
         val+=root->val;
         if(root->left==NULL && root->right==NULL)
         {
             if(sum==val) return true;
             return false;
         }
         return PathSum(root->left,sum,val) || PathSum(root->right,sum,val);

    }
    bool hasPathSum(TreeNode *root, int sum)
    {
       return PathSum(root,sum,0);
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 普通二叉树转换成搜索二叉树

    struct ListNode { int data; ListNode *lchild,*rchild; }; void CreateBST...

    用户1624346
  • 226 Invert Binary Tree

    /** * Definition for a binary tree node. * function TreeNode(val) { * thi...

    用户1624346
  • 二叉树遍历的非递归实现

    #include<stdio.h> #include<stack> #include<stdlib.h> using namespace std; struc...

    用户1624346
  • Linux中find命令的点滴积累

    find 命令在Linux中的作用非常强大,对于初学者来说,可能有很多的参数并不能很熟练的使用,导致无法充分发挥find的强大作用;本文对部分参数做初步的探索:

    qsjs
  • Centos7中find命令的用法,以及find+exec,find+xargs

    find . | xargs grep -ri ‘content’ //find . | xargs grep -ril ‘content’ 只显示文件名称 ...

    拓荒者
  • 建议收藏 | Linux常用命令

    cat,又是一个相对高频率的命令。比较官方的说法是命令用于链接文件并打印到标准输出设备上。这个文本输出命令可以用来查看文件内容,创建内容等,下面我们介绍几个比较...

    数字芯片社区
  • 014.Docker Harbor+Keepalived+LVS+共享存储高可用架构

    共享后端存储是一种比较标准的方案,将多个Harbor实例共享同一个后端存储,任何一个实例持久化到存储的镜像,都可被其他实例中读取。通过前置LB组件,如Keepa...

    木二
  • 15 道二叉树手写算法题(二)

    在上一期讲到,树和链表的手写算法题在面试中出现的频率最高。也正是因为这样,如果你马上就要参加面试,但之前没有刷多少算法题,那么很建议你先看看树和链表相关的题目。...

    乔戈里
  • admin3

    #################################################### 真机上实现别名的定义,修改配置文件

    py3study
  • Flat风格的Qml组合框

    Qt君

扫码关注云+社区

领取腾讯云代金券