data: 2018-12-26 21:02:10
原文鏈接

題目

給定兩個二叉樹，編寫一個函數(shù)來檢驗它們是否相同。

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

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

題目分析

樹狀圖形式肯定需要用到遞歸

解題思路

如果當前是最后可以確定且無子節(jié)點，則直接返回結(jié)果，否則需要繼續(xù)調(diào)用本方法進行遞歸

public boolean isSameTree(TreeNode p, TreeNode q) {
        //同時為null，表明無子節(jié)點，且該元素相同
        if(p == null && q == null){
            return true;
        // 其中一個不為null，表明兩個樹不相同
        }else if((p != null && q ==null) || (q != null && p ==null)){
            return false;
        }
        // 兩個值不相同，可以確定是不同的樹
        if(p.val != q.val){
            return false;
        }else{
        // 當前樹節(jié)點相同，但是無法判斷是否還有子節(jié)點，需要遞歸調(diào)用
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }

總結(jié)

本題屬于簡單題，遞歸調(diào)用本方法即可