Leetcode/src/main/java/com/fishercoder/solutions/secondthousand/_1325.java at master · fishercoder1534/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package com.fishercoder.solutions.secondthousand;

import com.fishercoder.common.classes.TreeNode;

/*
 * 1325. 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:
 *        1             1              1
 *       / \           / \              \
 *      2  3    ->    2  3    ->         3
 *     /  / \             \               \
 *    2   2 4             4               4
 *
 * 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:
 *          1          1
 *         / \        /
 *        3  3  ->   3
 *       / \          \
 *      3  2          2
 *
 * Input: root = [1,3,3,3,2], target = 3
 * Output: [1,3,null,null,2]
 *
 * Example 3:
 *         1              1            1          1
 *        /              /            /
 *       2              2            2
 *      /       ->     /      ->             ->
 *     2              2
 *    /
 *   2
 *
 * 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:
 *          1
 *         / \    ->
 *        1  1
 * Input: root = [1,1,1], target = 1
 * Output: []
 *
 * Example 5:
 *         1             1
 *        / \    ->     / \
 *       2  3          2  3
 *
 * Input: root = [1,2,3], target = 1
 * Output: [1,2,3]
 *
 * Constraints:
 * 1 <= target <= 1000
 * Each tree has at most 3000 nodes.
 * Each node's value is between [1, 1000].
 * */
public class _1325 {
    public static class Solution1 {
        /*
         * my original but verbose solution
         */
        public TreeNode removeLeafNodes(TreeNode root, int target) {
            while (hasTargetLeafNodes(root, target)) {
                root = removeLeafNodes(target, root);
            }
            return root;
        }

        private TreeNode removeLeafNodes(int target, TreeNode root) {
            if (root == null) {
                return root;
            }
            if (root.val == target && root.left == null && root.right == null) {
                root = null;
                return root;
            }
            if (root.left != null
                    && root.left.val == target
                    && root.left.left == null
                    && root.left.right == null) {
                root.left = null;
            }
            if (root.right != null
                    && root.right.val == target
                    && root.right.left == null
                    && root.right.right == null) {
                root.right = null;
            }
            removeLeafNodes(target, root.left);
            removeLeafNodes(target, root.right);
            return root;
        }

        private boolean hasTargetLeafNodes(TreeNode root, int target) {
            if (root == null) {
                return false;
            }
            if (root.left == null && root.right == null && root.val == target) {
                return true;
            }
            return hasTargetLeafNodes(root.left, target) || hasTargetLeafNodes(root.right, target);
        }
    }

    public static class Solution2 {
        /*A much more concise and efficient solution.*/
        public TreeNode removeLeafNodes(TreeNode root, int target) {
            if (root == null) {
                return root;
            }
            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;
        }
    }
}