問題鏈接

100. 相同的樹

問題描述

給你兩棵二叉樹的根節(jié)點 p 和 q ，編寫一個函數(shù)來檢驗這兩棵樹是否相同。

如果兩個樹在結(jié)構(gòu)上相同，并且節(jié)點具有相同的值，則認為它們是相同的。

示例

image.png

解題思路

這道題很簡單，驗證兩個樹的結(jié)構(gòu)以及節(jié)點上的值即可；
這道題非常適合初學(xué)者練習(xí)樹的深度優(yōu)先搜索以及廣度優(yōu)先搜索。

代碼示例（JAVA）

1. 深度優(yōu)先搜索

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);
    }
}

執(zhí)行結(jié)果

2. 廣度優(yōu)先搜索

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();
            // 校驗當前節(jié)點數(shù)據(jù)是否相同
            if (node1.val != node2.val) {
                return false;
            }
            // 校驗左右節(jié)點存在情況是否相同
            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();
    }
}

執(zhí)行結(jié)果