leetCode-相同的树

题目地址:相同的树

思路解析

文章思路来自左程云老师的算法新手班第六节

两个树相同需要满足结构相同并且每一个节点的值相同

如何保证结构相同,可以使用递归序去遍历,去判断每一个节点的左右分支的情况。

递归结束的条件自然是树被遍历完,下面全空,然后返回结果

同时需要判断节点处是否值相同

那么如何就是结构不相同呢,某一个节点为空,而另一个对应的节点不为空,那么就是结构不同,一定需要返回false,这时使用异或(^)(相同为假,不同为真)就可以判断

if(p == null ^ q == null){
    return false;
}

如果这个条件为假,那么说明这个节点要么同时存在,要么同时不存在,如果同时不存在,就说明树已经遍历完,无需接着判断,返回true即可

if (p == null&&q == null) {
    return true; 
}

如果节点同时不为空,就判断节点的值是否相同,该节点的左右节点是否也结构相同和值相同

所以,递归

return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);

下面是完整代码

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null ^ q == null){
            return false;
        }
        if (p == null&&q == null) {
           return true;
        }
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);
    }
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!

评论

  1. soso
    Android Chrome
    9月前
    2023-1-05 18:38:31

    顶啊

发送评论 编辑评论


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