前往
大廳
主題

LeetCode - 814. Binary Tree Pruning 解題心得

Not In My Back Yard | 2021-11-27 00:00:04 | 巴幣 2 | 人氣 211

題目連結:


題目意譯:
給定一個二元樹的根節點 head,回傳每個不包含任何一個 1 的子樹(對於給定的樹)都被移除後的樹。

一個節點的子樹為該節點加上其每個後代節點。

限制:
樹中的節點數位於範圍 [1, 200] 中。
Node.val 只會是 0 或是 1。



範例測資:
範例 1:
輸入: root = [1,null,0,0,1]
輸出: [1,null,0,null,1]
解釋:
只有紅色的節點滿足「每個子樹皆不含有 1」之性質。
圖中右側代表著答案。

範例 2:
輸入: root = [1,0,1,0,0,0,1]
輸出: [1,null,1,null,1]

範例 3:
輸入: root = [1,1,0,1,1,0,1,0]
輸出: [1,1,0,1,1,null,1]


解題思維:
遞迴解即可。我們利用深度優先搜尋(Depth First Search,DFS)去遞迴跑當前節點的左子樹以及右子樹。

當左子樹(或是右子樹)的節點值總和為 0,則代表該側沒有任何的 1,因此我們便將該側刪除(在這裡我們可以直接指向空位置(nullptr),儘管沒有直接刪除節點是一個不大好的習慣)。

然後本層的回傳值即為左子樹 + 右子樹 + 當前節點值。



不過因為有可能整個樹沒有任何的 1,所以整棵樹屆時會被刪個精光。因此,我們可以先行定義節點 dummy 一個用來指向(可以用左或右指標)給定的二元樹根節點 head。然後從 dummy 這個節點開始下去遞迴。最後只要回傳 dummy 指向的樹即可。




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

創作回應

更多創作