leetcode100-相同的树

原题

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:      1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:     1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:      1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

解法

思想

递归判断吧,两个树相同的条件是,左子树相同且右子树相同且根节点的值相等;或者两个根节点都是null。

代码

一行代码极简风格

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return (p==null && q==null) || (q!=null && p!= null && p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right));
    }
}

拆分出来的条件是:
(p==null && q==null):两个根节点都为null,或者

(q!=null && p!= null && p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right)):两个根节点都不为null,且各自对应的左右子树相同。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode100-%e7%9b%b8%e5%90%8c%e7%9a%84%e6%a0%91/