Recursive Depth First Search Algorithm to Delete Leaves With a G

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

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

推荐阅读：
#DiningForBrussels: How Belgium Is Fighting Terrorism With A For　 Many WordPress Site Hackings Caused To These Plugins　 GoDaddy Company Now Hosts New Enterprise-Level Plans　 Using Reduce to Count the Array in Javascript　 Several Algorithms to Compute the Score of Parentheses　 Two Pointer Algorithm to Find Maximum Two Sum Less Than K　 Algorithm to Delete a Character to Make a Valid Palindrome　 The Dynamic Programming Algorithm to Compute the Minimum Falling　 Javascript’s toFixed Implementation without Rounding　 Algorithm to Count the Minimum Add to Make Parentheses Valid　
评论列表
添加评论