題目連結:
題目意譯:
給定兩個二元樹,撰寫一個函式去檢查兩棵樹是否相同。
當兩著結構相同、且節點的值皆一致時,兩個二元樹可被視為相同的。
範例測資:
範例 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
範例 2:
輸入: 1 1
/ \ / \
2 1 1 2
[1,2,1] [1,1,2]
輸出: false
解題思維:
遞迴即可。如以下,
終止條件:檢查兩棵樹目前指到的節點是否兩者是否皆為空指標。如果是則回傳「真」(true)。如果只有一個為空,則不用繼續遞迴,回傳「假」(false)。如果兩者非空,則檢查兩者指到的節點之值是否一樣。如果不一樣,則回傳「假」(false)
遞迴(狀態轉移)條件:反之,遞迴比較目前兩棵樹的節點 p 、q 各自的左子樹(p->left 、 q->left)以及右子樹(p->right 、 q->right)是否各自相同。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。