相同的樹（遞歸實作）

題目

給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

示例 :

注意點

1、确定遞歸出口：

• 兩棵樹都為空時；
• 當一棵樹為空，另一棵樹還有節點時；
• 兩棵樹同一節點的值不同時。

2、确定遞歸情況：遞歸判斷左右子樹。（使用“&&”是因為所有節點都相同才算相同）

實作

public boolean isSameTree(TreeNode p, TreeNode q) {
    
    	//當兩棵樹都為空時，傳回true
        if(p == null && q == null) return true;
        //當一棵樹為空，另一棵樹還有節點時，傳回false
        if(p == null || q == null) return false;
        //當兩棵樹同一節點的值不同時，傳回false
        if(p.val != q.val) return false;
		
		//遞歸判斷左右子樹
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }