🔗 🟡 1325. Delete Leaves With a Given Value 1407

tags: `Weekly Contest 172` `遞迴(Recursion)`

題意

給定一個二元樹的根節點 $root$ 和一個整數 $target$ ，刪除所有值為 $target$ 的葉節點。

注意，若刪除後父節點變成葉節點且值為 $target$ ，則該節點也應該被刪除，直到無法再刪除為止。

思路：遞迴(Recursion)

由於若刪除後父節點變成符合條件的葉節點，也需要繼續刪除，因此可以使用 遞迴(Recursion) 來解決。

根據遞迴的特性，會從最底層的葉節點開始判斷是否符合條件，若該節點為空或應該被刪除，則返回空節點，否則返回原節點。而根據子節點的返回值是否為空間點，又能判斷當前節點是否在變成了葉節點，若是則繼續刪除，一直往上回到根節點。

這裡不得不提到遞迴的另外一個翻譯：遞歸。將往下的過程稱為 遞，而往上的過程稱為 歸 ，這裡的 歸 是指到達遞歸終止條件後，往上歸併解決問題的過程。在本題中， 歸 就是根據子節點的返回值，判斷應如何操作當前節點，並繼續往上的過程。

複雜度分析

時間複雜度： $O(n)$ 。
空間複雜度： $O(n)$ ，遞迴所使用的Stack空間，為樹的高度，最壞情況下為 $O(n)$ 。

class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if not root:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        return None if not root.left and not root.right and root.val == target else root

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (root == nullptr) return nullptr;
        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);
        return (root->left == nullptr and root->right == nullptr and root->val == target) ? nullptr : root;
    }
};