Recursive Depth First Search Algorithm to Delete Leaves With a G

  • 时间：2020-09-12 10:06:27
  • 分类：网络文摘
  • 阅读：137 次

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:
binary-tree-delete-leaves-1 Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree algorithms c / c++ DFS java javascript python
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:
binary-tree-delete-leaves-2 Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree algorithms c / c++ DFS java javascript python
Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

Example 3:
binary-tree-delete-leaves-3 Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree algorithms c / c++ DFS java javascript python
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
Each tree has at most 3000 nodes.
Each node’s value is between [1, 1000].

Hints:
Use the DFS to reconstruct the tree such that no leaf node is equal to the target. If the leaf node is equal to the target, return an empty object instead.

Recursive DFS Algorithm to Delete Leaves of a Binary Tree with a Target Value

We can recursively construct the binary tree using Depth First Search Algorithm: when the node value equals the target value, we need to check if it eventually will be a leaf node. If yes, we need to set it to NULL otherwise, leave it as it is.

The return value of the recursive function will be the final value of the current node, thus, making it possible for parents to delete the intermediate leave nodes (that are equal to the target value).

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

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

The above implementation could be improved to a much concise version:

C++:

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (root == nullptr) return nullptr;
        if (root->left) {
            root->left = removeLeafNodes(root->left, target);
        }
        if (root->right) {
            root->right = removeLeafNodes(root->right, target);
        }
        // both left and right are NULL, that is, current is a leaf node
        if (root->left == root->right && root->val == target) {
            return nullptr;
        }
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (root == nullptr) return nullptr;
        if (root->left) {
            root->left = removeLeafNodes(root->left, target);
        }
        if (root->right) {
            root->right = removeLeafNodes(root->right, target);
        }
        // both left and right are NULL, that is, current is a leaf node
        if (root->left == root->right && root->val == target) {
            return nullptr;
        }
        return root;
    }
};

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

Javascript:

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {TreeNode}
 */
var removeLeafNodes = function(root, target) {
    if (!root) return null;
    if (root.left) {
        root.left = removeLeafNodes(root.left, target);
    }
    if (root.right) {
        root.right = removeLeafNodes(root.right, target);
    }
    if (root.left == root.right && root.val == target) {
        return null;
    }
    return root;      
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {TreeNode}
 */
var removeLeafNodes = function(root, target) {
    if (!root) return null;
    if (root.left) {
        root.left = removeLeafNodes(root.left, target);
    }
    if (root.right) {
        root.right = removeLeafNodes(root.right, target);
    }
    if (root.left == root.right && root.val == target) {
        return null;
    }
    return root;      
};

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
        if root is None:
            return None
        if not (root.left is None):
            root.left = self.removeLeafNodes(root.left, target)
        if not (root.right is None):
            root.right = self.removeLeafNodes(root.right, target)
        if root.left == root.right and root.val == target:
            return None
        return root           
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
        if root is None:
            return None
        if not (root.left is None):
            root.left = self.removeLeafNodes(root.left, target)
        if not (root.right is None):
            root.right = self.removeLeafNodes(root.right, target)
        if root.left == root.right and root.val == target:
            return None
        return root

Both space and time complexity of all above implementations are O(N) where N is the number of the nodes in the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
官员竟然称质疑转基因食品是民众无知　 转基因食品的利与弊及潜在危害浅析　 食品安全法即将修订 有奖举报或将入法　 辽宁省曝光十大食品犯罪典型案例　 几种转基因与非转基因食物的差别　 判断是否为转基因食品的简单方法　 转基因食品与肿瘤等高度相关引关注　 善意的谎言：莫须有的健康食品排行榜　 曝光13种假保健食品检出药物成分　 高纤维饼干口感好是靠油脂“润滑”　
评论列表
添加评论