經(jīng)典Java面試題解析：判斷兩個(gè)二叉樹是否相同

在Java的面試中，判斷兩個(gè)二叉樹是否相同是一個(gè)常見的算法問題。本文將介紹一道經(jīng)典的Java面試題——判斷兩個(gè)二叉樹是否相同，并提供詳細(xì)的解析和解題思路。

題目

給定兩個(gè)二叉樹，判斷它們是否相同（即結(jié)構(gòu)相同且節(jié)點(diǎn)的值相同）。

解析與解題思路

判斷兩個(gè)二叉樹是否相同可以使用遞歸的方式來實(shí)現(xiàn)。

1. 如果兩個(gè)二叉樹都為空，則它們相同，返回true。
2. 如果兩個(gè)二叉樹中有一個(gè)為空而另一個(gè)不為空，則它們不相同，返回false。
3. 如果兩個(gè)二叉樹的根節(jié)點(diǎn)的值不相同，則它們不相同，返回false。
4. 否則，遞歸地判斷兩個(gè)二叉樹的左子樹和右子樹是否相同。

以下是Java代碼實(shí)例：

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

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

public class SameTree {
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true; // 兩個(gè)二叉樹都為空，相同
        } else if (p == null || q == null) {
            return false; // 一個(gè)二叉樹為空，一個(gè)二叉樹不為空，不相同
        } else if (p.val != q.val) {
            return false; // 兩個(gè)二叉樹的根節(jié)點(diǎn)值不相同，不相同
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 遞歸判斷左子樹和右子樹是否相同
        }
    }

    public static void main(String[] args) {
        /*
         * 構(gòu)造兩個(gè)二叉樹：
         *  二叉樹1：
         *      1
         *     / \
         *    2   3
         *
         *  二叉樹2：
         *      1
         *     / \
         *    2   3
         */
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);

        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(3);

        boolean result = isSameTree(p, q);
        System.out.println("兩個(gè)二叉樹是否相同：" + result);
    }
}

輸出結(jié)果：

兩個(gè)二叉樹是否相同：true

結(jié)論

通過遞歸的方式，我們可以判斷兩個(gè)二叉樹是否相同。判斷二叉樹相同的條件是：兩個(gè)二叉樹的根節(jié)點(diǎn)值相同，并且它們的左子樹和右子樹也相同。掌握了解題思路和實(shí)現(xiàn)代碼，我們能夠在面試中更加自信地回答相關(guān)問題。

  學(xué)java，就到java編程獅！