Depth First Search Algorithm to Delete Insufficient Nodes in Roo

  • 时间:2020-09-11 08:17:29
  • 分类:网络文摘
  • 阅读:89 次

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf. (A leaf is a node with no children.) A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit. Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

insufficient-nodes-in-binary-tree-300x110 Depth First Search Algorithm to Delete Insufficient Nodes in Root to Leaf Paths in Binary Tree algorithms c / c++ java recursive

insufficient-nodes-in-binary-tree

Example 1:
Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
Output: [1,2,3,4,null,null,7,8,9,null,14]

Example 2:
Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
Output: [5,4,8,11,null,17,4,7,null,null,null,5]

Example 3:
Input: root = [1,2,-3,-5,null,4,null], limit = -1
Output: [1,null,-3,4]

Note:

The given tree will have between 1 and 5000 nodes.
-10^5 <= node.val <= 10^5
-10^9 <= limit <= 10^9

DFS Algorithm: Passing the Limit From Root to Leaves

Let’s solve this in DFS (Depth First Search) Algorithm – which to be implemented in Recursion. The limit is passed down from the Root to the leaves. The terminating condition is when node is NULL which of course, we return NULL. And when node is a leaf node, we check if the value is small than the current limit – if yes, it is a insufficient node – which will be removed – return NULL.

Otherwise, recursively, we update the left and right child of the current node. And return NULL if both are NULL (meaning all the sub trees are removed).

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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* sufficientSubset(TreeNode* root, int limit) {
        if (!root) return root;
        if (root->left == nullptr && root->right == nullptr) {
            if (root->val < limit) return nullptr;
            return root;
        }
        root->left = sufficientSubset(root->left, limit - root->val);
        root->right = sufficientSubset(root->right, limit - root->val);
        return root->left || root->right ? root : nullptr;
    }
};
/**
 * 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* sufficientSubset(TreeNode* root, int limit) {
        if (!root) return root;
        if (root->left == nullptr && root->right == nullptr) {
            if (root->val < limit) return nullptr;
            return root;
        }
        root->left = sufficientSubset(root->left, limit - root->val);
        root->right = sufficientSubset(root->right, limit - root->val);
        return root->left || root->right ? root : nullptr;
    }
};

And 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
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root == null) {
            return null;
        }
        if (root.left == root.right) {
            if (root.val < limit) {
                return null;
            }
            return root;
        }
        root.left = sufficientSubset(root.left, limit - root.val);
        root.right = sufficientSubset(root.right, limit - root.val);
        return root.left == root.right ? null : 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 sufficientSubset(TreeNode root, int limit) {
        if (root == null) {
            return null;
        }
        if (root.left == root.right) {
            if (root.val < limit) {
                return null;
            }
            return root;
        }
        root.left = sufficientSubset(root.left, limit - root.val);
        root.right = sufficientSubset(root.right, limit - root.val);
        return root.left == root.right ? null : root;
    }
}

We can test the equality for left and right node – if they are equal – then both nodes are NULL. The overall complexity is O(N) where N is the number of the nodes in the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
诗词名句鉴赏:身既死兮神以灵,魂魄毅兮为鬼雄!  诗词名句鉴赏:嘤其鸣矣,求其有声。  数学题:化肥厂计划用15天生产化肥4500吨  数学题:学校把两捆树苗分给三个年级种植  数学题:甲乙丙三人的平均年龄为22岁  数学题:在一块边长60m的正方形花坛四边种冬青树  数学题:用一根铁丝刚好焊成一个棱长10厘米的正方体框架  数学题:一艘船在静水中每小时行驶40千米  数学题:在AB两点之间等距离安装路灯  数学题:一种商品随季节出售 
评论列表
添加评论