leetCode-路径总和

题目地址:路径总和

解题思路

本文解题思路来自左程云老师算法课新手班第七节

每一条路径都是最后到达尾部节点,也就是这个节点的左右都为空,这时,sum和累加值相同才是true

在方法体外,设置一个静态变量isSum,初始值弄为false。

process方法需要三个参数,一个为节点,一个为已经累加的preSum,一个为要求的Sum 。

在process方法内改变这个isSum。

        if (x.left==null&&x.right==null){
            if (preSum+x.val==sum){
                isSum = true;
            }
            return;
        }

然后去维护preSum,

preSum+= x.val;

去递归

        if(x.left!=null){
            process(x.left, preSum, sum);
        }
        if (x.right != null) {
            process(x.right, preSum, sum);
        }

接下来是要写要调用的那个函数,边界判断一下就ok

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        isSum = false;
        process(root,0,targetSum);
        return isSum;
    }

完整代码

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
	     return false;
        }
	isSum = false;
        process(root,0,targetSum);
        return isSum;
    }
    public static boolean isSum = false;
    public static void process(TreeNode x,int preSum,int sum){
        
        if (x.left==null&&x.right==null){
            if (preSum+x.val==sum){
                isSum = true;
            }
            return;
        }
        preSum+= x.val;
        if(x.left!=null){
            process(x.left, preSum, sum);
        }
        if (x.right != null) {
            process(x.right, preSum, sum);
        }
    }

需要注意的问题

在 hasPathSum函数内的这句话必不可少

isSum = false;

在leetCode判题中,静态变量并不会每次都更新为初始值,需要手动更新,

假如上一题isSum变为了 true,在这题中isSum的初始值还是true,假如这题答案为false,也就是isSum不存在变化,因为没有初始化,那么最后还是true,判题出现错误。

不知道算是bug还是啥,反正自己注意一下。

版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
春节
快乐