LC 100.相同的树

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

示例 1：

输入： p = [1,2,3], q = [1,2,3]
输出： true

示例 2：

输入： p = [1,2], q = [1,null,2]
输出： false

示例 3：

输入： p = [1,2,1], q = [1,1,2]
输出： false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
$-10^4 \leq Node.val \leq 10^4$

解法一(递归)

思路分析：

采用与LC101.对称二叉树相同的思路来解决

实现代码如下：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        return p.val == q.val
                && isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right);
    }
}

提交结果如下：

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.2 MB,击败了5.00% 的Java用户

复杂度分析：

时间复杂度： $O (n)$
空间复杂度： $O (n)$

解法二(迭代)

思路分析：

依旧是与LC101.对称二叉树相同的思路来解决，但是此处使用一个双端队列来代替两个栈
即第一个二叉树主要进队出队在队列左端；第二个二叉树主要进队出队在队列右端

实现代码如下：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(p);
        deque.offerLast(q);
        while (!deque.isEmpty()) {
            TreeNode left = deque.pollFirst();
            TreeNode right = deque.pollLast();
            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;

            // 两者采用一样的遍历顺序 中左右 所以 右指针先进栈 再左指针进栈
            deque.offerFirst(left.right);
            deque.offerFirst(left.left);
            deque.offerLast(right.right);
            deque.offerLast(right.left);
        }
        return true;
    }

}