Google Interview Question — LeetCode 1325

In this post, we are going to discuss leetcode 1325 — Delete Leaves With a Given Value, which is recently asked in Google interviews.

Problem Analysis

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).

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2 
Output: [1,null,3,null,4] 
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

Input: root = [1,3,3,3,2], target = 3 
Output: [1,3,null,null,2]

This is a DFS tree traversal problem.

My Thinking Process

For this question, we need to remove the leaves with a given value. The tricky part is, after generated the new tree, we need to recursively delete the new leaves with the given value.

This is a typical post-order DFS problem. I.e., to traverse the children nodes first, then process the current node.

Code Implementation

Base on the analysis above, below is my implementation of the problem.