[LeetCode] 1325. Delete Leaves With a Given Value

https://leetcode.com/problems/delete-leaves-with-a-given-value/description/

leetcode - Delete Leaves With a Given Value

문제 유형 : 이진트리, dfs, 재귀

문제 난이도 : Medium

 

문제

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).

 

이진트리의 루트와 정수 target이 주어진다.

leaf노드의 값이 target인 경우, 노드를 삭제하라.

만약 리프노드를 삭제하고 새로운 리프노드도 target인경우에도 계속 지워줘야 한다.

 

풀이

후위순회로 풀 수 있다.

만약 루트가 null이면, null을 반환한다.

자식 노드들부터 재귀호출을 통해 구한다.

만약 자식노드가 둘다 null이고, 자신의 값이 target이면, null을 반환하고, 아니라면 자기 자신을 반환하면 된다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (!root) return nullptr;
        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);
        if (root->val == target && !root->left && !root->right) return nullptr;
        return root;
    }
};