#100. Same Tree

題目描述

給你兩個二元樹p、q的根節點，寫一個函式來檢查兩個樹是否是一樣的樹。

如果兩個二元樹是一樣的，它們的結構和節點值都會是一樣的。

限制條件

節點數量為[0,100]。
-10^4 <= 節點值 <= 10^4

解題思路

如果兩棵樹是一樣的，用同樣的查詢方式得到的結果也會是一樣的，因此我們只要用查詢樹的方法並且同時查詢和比對兩顆樹，就可以知道結果。

比對的判斷有三個條件：

如果兩個節點都是空的則是一樣的。
兩個相同的節點不會出現一個是空節點一個不是空節點的情形。
相同的節點，兩個節點的值會是一樣的。

Traversal

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

複雜度分析：

時間複雜度：要確實檢查每個節點，因此時間複雜度為O(n)。
空間複雜度：會需要等所有的節點都檢查完才能夠結束函式堆疊，因此空間複雜度為O(n)。

學習重點

二元樹走訪(Traversal)。