LeetCode - Medium - 1325. Delete Leaves With a Given Value

以你之姓@ 2022-10-12 15:53 24阅读 0赞

## Topic ##

*  Hash Table
 *  Tree
 *  Binary Tree
 *  Depth-First Search
 *  Breadth-First Search

## Description ##

[https://leetcode.com/problems/delete-leaves-with-a-given-value/][https_leetcode.com_problems_delete-leaves-with-a-given-value]

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 it’s parent node becomes a leaf node and has the value `target`, it should also be deleted (you need to continue doing that until you can’t).

**Example 1:**

![45158eba8aaae4f5286c3041cd8c4a25.png][]

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:**

![deff515d4452a1460d7add041447b7fa.png][]

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

**Example 3:**

![e2a9fdd0e1216feb8eb1c7e05a4950d4.png][]

Input: root = [1,2,null,2,null,2], target = 2
    Output: [1]
    Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

**Example 4:**

Input: root = [1,1,1], target = 1
    Output: []

**Example 5:**

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

**Constraints:**

*  `1 <= target <= 1000`
 *  The given binary tree will have between `1` and `3000` nodes.
 *  Each node’s value is between `[1, 1000]`.

## Analysis ##

用到后序遍历模式。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class DeleteLeavesWithAGivenValue { 
        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;
        	return root;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class DeleteLeavesWithAGivenValueTest { 
    
        @Test
        public void test() { 
            DeleteLeavesWithAGivenValue dObj = new DeleteLeavesWithAGivenValue();
    
            TreeNode root1 = BinaryTree.of(1, 2, 3, 2, null, 2, 4);
            TreeNode expected1 = BinaryTree.of(1, null, 3, null, 4);
            assertTrue(BinaryTree.equals(dObj.removeLeafNodes(root1, 2), expected1));
            
            TreeNode root2 = BinaryTree.of(1, 3, 3, 3, 2);
            TreeNode expected2 = BinaryTree.of(1, 3, null, null, 2);
            assertTrue(BinaryTree.equals(dObj.removeLeafNodes(root2, 3), expected2));
            
            TreeNode root3 = BinaryTree.of(1, 2, null, 2, null, 2);
            TreeNode expected3 = BinaryTree.of(1);
            assertTrue(BinaryTree.equals(dObj.removeLeafNodes(root3, 2), expected3));
            
            TreeNode root4 = BinaryTree.of(1, 1, 1);
            TreeNode expected4 = null;
            assertTrue(BinaryTree.equals(dObj.removeLeafNodes(root4, 1), expected4));
            
            TreeNode root5 = BinaryTree.of(1, 2, 3);
            TreeNode expected5 = BinaryTree.of(1, 2, 3);
            assertTrue(BinaryTree.equals(dObj.removeLeafNodes(root5, 1), expected5));
        }
    }

[https_leetcode.com_problems_delete-leaves-with-a-given-value]: https://leetcode.com/problems/delete-leaves-with-a-given-value/
[45158eba8aaae4f5286c3041cd8c4a25.png]: /images/20221005/df9b1023315a4df3b70ef497d1f33388.png
[deff515d4452a1460d7add041447b7fa.png]: /images/20221005/abc4e887186d4582a7e020be0c737a32.png
[e2a9fdd0e1216feb8eb1c7e05a4950d4.png]: /images/20221005/5fad7b5302884fb19122b96e00a83058.png