切換
舊版
前往
大廳
主題

LeetCode - 404. Sum of Left Leaves 解題心得

Not In My Back Yard | 2020-10-15 00:01:32 | 巴幣 2 | 人氣 113

題目連結:


題目意譯:
計算給定的二元樹之所有左子葉之值的總和。



範例測資:
範例:
  3
 / \
9  20
  /  \
 15   7

這棵樹有兩個左子葉,值分別是 9 和 15。因此回傳 24。


解題思維:
如果這棵樹為空,或是只有根節點一個節點,則直接回傳 0 。

則定義一函式 F(treeNode *now) ,
當 now->left == NULL 且 now->right == NULL ,則代表 now 指到的節點是我們要的左子葉(上面已經判掉只有根節點的情況,而下面會避免找到右子葉),因此將回傳 now->value。

如果上面的判斷式為非,則定義一變數 sums 用以存左子樹的左子葉總和 + 右子樹的左子葉總和。

如果 now->left 不為空,則代表 now 有左子樹。因此將 sums 加上 F(now->left)。

如果 now->right 不為空且 now->right->left 、 now->right->right 兩者之一不為空,則代表 now 的右子樹不為空,且也不是右子葉。所以將 sums 加上 F(now->right)。

最後回傳 sums 。而最外層呼叫 F(root) 的回傳結果即是所求(root 代表根節點)。




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

創作回應

更多創作