Recursive Depth First Search Algorithm to Delete Leaves With a G

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

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

推荐阅读：
5 Tips for Capturing More Leads on Your Blog　 Don’t Fall Victim to the Content Overproduction Trap　 Are You Taking Advantage Of These Free WordPress Marketing Plugi　 What Content Marketers Can Learn from Game of Thrones　 All You Need To Know About How Small Business Should Handle Soci　 Should You Add Live Chat to Your Blog?　 Food Blogger Accuses Fast Food Giant Of Stealing His Recipe　 Back To School 2016: How To Rock (And Profit) With Sales And Mar　 The Five Fundamentals to Creating a Powerhouse Blog　 Blog On The Go With These Mobile Apps　
评论列表
添加评论