20190503-相同的樹
- 2020 年 1 月 16 日
- 筆記
相同的樹
難度分類
簡單
題目描述
給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。
如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。
示例 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
示例 3:
輸入: 1 1
/ /
2 1 1 2
[1,2,1], [1,1,2]
輸出: false
演算法
採用層序遍歷只要結構或值不相等就返回False，使用遞歸解該題具體思路如下：
- 遞歸的結束條件：當比較的treeNode的值都為None的時候返回True
- 遞歸條件：比較2個treeNode的val,當val相等的時候比較2個TreeNode的左子樹和右子樹
考點
- 遞歸
- And運算
程式碼
def isSameTree(p, q): if p is None and q is None: return True else: if p and q: if p.val == q.val:#判斷當前樹節點的值是否相等 return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) else: return False#如果不相等，則返回False else: return False
