Recursive Depth First Search Algorithm to Delete Leaves With a G

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

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类富含维生素的食物给眼睛补营养　 人工营养素和天然营养素有何区别　 红枣养生食疗：养肝排毒安神补血养颜　 常吃些鲜枣可抑制癌细胞提高免疫力　 保健与养生：大枣的食疗功效和作用　 红枣食疗三推荐：健脾安神降压降脂　 男性养生：男人吃葡萄干有特别好处　 食品营养之葡萄干具有的营养价值　 女性养生：女人吃葡萄干有哪些好处？　 对转基因食品必须采取最严格保护措施　
评论列表
添加评论