切換
舊版
前往
大廳
主題

LeetCode - 100. Same Tree 解題心得

Not In My Back Yard | 2020-08-12 01:18:49 | 巴幣 4 | 人氣 193

題目連結:


題目意譯:
給定兩個二元樹,撰寫一個函式去檢查兩棵樹是否相同。

當兩著結構相同、且節點的值皆一致時,兩個二元樹可被視為相同的。



範例測資:
範例 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)是否各自相同。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作