1325-kir3i.md

1325. Delete Leaves With a Given Value

Solution

• 시간복잡도: O(N)

• 알고리즘

  트리 순회

• 풀이설명

  1. 트리를 후위순회하면서 다음 조건을 체크합니다.
     • 리프노드인지
     • val이 target과 같은 값인지
  2. 삭제 조건에 합당한 경우 null을 반환합니다. 그렇지 않은 경우 노드를 그대로 반환합니다.
  3. 후위순회의 특성상 리프노드부터 순회하기 때문에 결국 원하는 형태의 트리가 나옵니다.

• 소스코드

  • C++

    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->left && !root->right && root->val == target)
                return nullptr;
            else
                return root;
        }
    };

  • Python

    class Solution:
        def removeLeafNodes(self, root, target):
            if not root:
                return None
            root.left = self.removeLeafNodes(root.left, target)
            root.right = self.removeLeafNodes(root.right, target)
            if not root.left and not root.right and root.val == target:
                return None
            else:
                return root

  • Java

    class Solution {
        public TreeNode removeLeafNodes(TreeNode root, int target) {
            if(root == null)   return null;
            root.left = removeLeafNodes(root.left, target);
            root.right = removeLeafNodes(root.right, target);
            if(root.left == null && root.right == null && root.val == target)
                return null;
            else
                return root;
        }
    }