题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

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

题解

此题是另外一道题的一个子解题步骤：另一个树的子树，根据题目描述，我们可以使用深度优先搜索，首先判断如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同【这也是递归的终止条件】。然后判断两个树的根节点值是否相同，接下来递归的方式处理两个树的左子树和右子树，如果都相同，则为相同的树。

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

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

复杂度分析

时间复杂度：O(min(m, n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。
空间复杂度：O(min(m, n))，其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。