LeetCode：100. 相同的树

问题链接

100. 相同的树

问题描述

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

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

示例

image.png

解题思路

这道题很简单，验证两个树的结构以及节点上的值即可；
这道题非常适合初学者练习树的深度优先搜索以及广度优先搜索。

代码示例（JAVA）

1. 深度优先搜索

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

执行结果

2. 广度优先搜索

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null || p.val != q.val) {
            return false;
        }

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            // 校验当前节点数据是否相同
            if (node1.val != node2.val) {
                return false;
            }
            // 校验左右节点存在情况是否相同
            if ((node1.left == null && node2.left != null) || node1.left != null && node2.left == null) {
                return false;
            }
            if ((node1.right == null && node2.right != null) || node1.right != null && node2.right == null) {
                return false;
            }

            if (node1.left != null) {
                queue1.offer(node1.left);
                queue2.offer(node2.left);
            }
            if (node1.right != null) {
                queue1.offer(node1.right);
                queue2.offer(node2.right);
            }
        }

        return queue1.isEmpty() && queue2.isEmpty();
    }
}

执行结果