Recursive Depth First Search Algorithm to Delete Leaves With a G

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

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

推荐阅读：
4 Things You Need to Know When Funding Your Freelance Business　 How Dedicated Servers Boost the Performance of A Business Blog　 Irish Travel Blogger Visits Every Country In The World, Just In 　 How to Build an Online Store on WordPress Using WooCommerce　 C++ Coding Reference: is_sorted_until() and is_sorted()　 Two Rectangles Overlap Detection Algorithm in C++　 C++ Coding Reference: next_permutation() and prev_permutation()　 C++ Coding Reference: count and count_if　 How to Reorder Data in Log Files using the Custom Sorting Algori　 C++ Coding Reference: std::accumulate() and examples　
评论列表
添加评论