题目描述

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

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

示例 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

https://leetcode-cn.com/problems/same-tree/

解法1

两棵树相同的定义是结构上相同，且对应位置的值相同。我们首先考虑两颗二叉树，每个二叉树是由3个节点构成的满二叉树。先对比跟节点，如果跟节点的值不相同那么就不用继续比了。如果跟节点的值相同，再分别对比两棵树的左右叶子结点。将上面的过程一般化，如果树由多层的节点构成，我们需要递归的对比左右子树。如果节点缺失了左/右子树，那么另一颗树的相应位置也应该为null。

我们按照上面的说明编写代码，时间复杂度为O(n)，空间复杂度为O(n)（树为“线性的“情况下，调用栈的开销），n为节点数量。全部代码如下：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        else if (p != null && q != null) {
            if (p.val != q.val)
                return false;
        } else // q与q一个为空，另一个不为空
            return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}