題目連結:
題目意譯:
計算給定的二元樹之所有左子葉之值的總和。
範例測資:
範例:
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 代表根節點)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。