Skip to content

Commit 4a7c050

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1080
No.1080.Insufficient Nodes in Root to Leaf Paths
1 parent 4014528 commit 4a7c050

File tree

7 files changed

+232
-50
lines changed

7 files changed

+232
-50
lines changed

‎solution/1000-1099/1080.Insufficient Nodes in Root to Leaf Paths/README.md

Lines changed: 81 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,11 @@
5151

5252
<!-- 这里可写通用的实现逻辑 -->
5353

54-
递归遍历整棵树，如果到达叶子结点且路径和小于 limit，直接返回 null 表示删除。如果左右子树都被删除，说明经过当前结点的路径和也一定小于 limit，同样需要删除
54+
**方法一：递归**
55+
56+
递归遍历整棵树，如果到达叶子结点且路径和小于 $limit$，直接返回 `null` 表示删除。如果左右子树都被删除，说明经过当前结点的路径和也一定小于 $limit$，同样需要删除。
57+
58+
时间复杂度 $O(n)$，其中 $n$ 是二叉树节点的个数。
5559

5660
<!-- tabs:start -->
5761

@@ -60,28 +64,46 @@
6064
<!-- 这里可写当前语言的特殊实现逻辑 -->
6165

6266
```python
67+
# Definition for a binary tree node.
68+
# class TreeNode:
69+
# def __init__(self, val=0, left=None, right=None):
70+
# self.val = val
71+
# self.left = left
72+
# self.right = right
6373
class Solution:
64-
def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
74+
def sufficientSubset(
75+
self, root: Optional[TreeNode], limit: int
76+
) -> Optional[TreeNode]:
6577
if root is None:
6678
return None
67-
6879
limit -= root.val
6980
if root.left is None and root.right is None:
7081
return None if limit > 0 else root
71-
7282
root.left = self.sufficientSubset(root.left, limit)
7383
root.right = self.sufficientSubset(root.right, limit)
74-
75-
if root.left is None and root.right is None:
76-
return None
77-
return root
84+
return None if root.left is None and root.right is None else root
7885
```
7986

8087
### **Java**
8188

8289
<!-- 这里可写当前语言的特殊实现逻辑 -->
8390

8491
```java
92+
/**
93+
* Definition for a binary tree node.
94+
* public class TreeNode {
95+
* int val;
96+
* TreeNode left;
97+
* TreeNode right;
98+
* TreeNode() {}
99+
* TreeNode(int val) { this.val = val; }
100+
* TreeNode(int val, TreeNode left, TreeNode right) {
101+
* this.val = val;
102+
* this.left = left;
103+
* this.right = right;
104+
* }
105+
* }
106+
*/
85107
class Solution {
86108
public TreeNode sufficientSubset(TreeNode root, int limit) {
87109
if (root == null) {
@@ -101,6 +123,14 @@ class Solution {
101123
### **Go**
102124

103125
```go
126+
/**
127+
* Definition for a binary tree node.
128+
* type TreeNode struct {
129+
* Val int
130+
* Left *TreeNode
131+
* Right *TreeNode
132+
* }
133+
*/
104134
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
105135
if root == nil {
106136
return nil
@@ -127,22 +157,57 @@ func sufficientSubset(root *TreeNode, limit int) *TreeNode {
127157
### **C++**
128158

129159
```cpp
160+
/**
161+
* Definition for a binary tree node.
162+
* struct TreeNode {
163+
* int val;
164+
* TreeNode *left;
165+
* TreeNode *right;
166+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
167+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
168+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
169+
* };
170+
*/
130171
class Solution {
131172
public:
132173
TreeNode* sufficientSubset(TreeNode* root, int limit) {
133-
if (root == nullptr) return nullptr;
134-
174+
if (!root) return nullptr;
135175
limit -= root->val;
136-
if (root->left == nullptr && root->right == nullptr)
137-
return limit > 0 ? nullptr : root;
138-
176+
if (!root->left && !root->right) return limit > 0 ? nullptr : root;
139177
root->left = sufficientSubset(root->left, limit);
140178
root->right = sufficientSubset(root->right, limit);
179+
return !root->left && !root->right ? nullptr : root;
180+
}
181+
};
182+
```
141183
142-
if (root->left == nullptr && root->right == nullptr)
143-
return nullptr;
144-
return root;
184+
### **JavaScript**
185+
186+
```js
187+
/**
188+
* Definition for a binary tree node.
189+
* function TreeNode(val, left, right) {
190+
* this.val = (val===undefined ? 0 : val)
191+
* this.left = (left===undefined ? null : left)
192+
* this.right = (right===undefined ? null : right)
193+
* }
194+
*/
195+
/**
196+
* @param {TreeNode} root
197+
* @param {number} limit
198+
* @return {TreeNode}
199+
*/
200+
var sufficientSubset = function(root, limit) {
201+
if (!root) {
202+
return null;
203+
}
204+
limit -= root.val;
205+
if (!root.left && !root.right) {
206+
return limit > 0 ? null : root;
145207
}
208+
root.left = sufficientSubset(root.left, limit);
209+
root.right = sufficientSubset(root.right, limit);
210+
return !root.left && !root.right ? null : root;
146211
};
147212
```
148213

‎solution/1000-1099/1080.Insufficient Nodes in Root to Leaf Paths/README_EN.md

Lines changed: 76 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -48,26 +48,44 @@
4848
### **Python3**
4949

5050
```python
51+
# Definition for a binary tree node.
52+
# class TreeNode:
53+
# def __init__(self, val=0, left=None, right=None):
54+
# self.val = val
55+
# self.left = left
56+
# self.right = right
5157
class Solution:
52-
def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
58+
def sufficientSubset(
59+
self, root: Optional[TreeNode], limit: int
60+
) -> Optional[TreeNode]:
5361
if root is None:
5462
return None
55-
5663
limit -= root.val
5764
if root.left is None and root.right is None:
5865
return None if limit > 0 else root
59-
6066
root.left = self.sufficientSubset(root.left, limit)
6167
root.right = self.sufficientSubset(root.right, limit)
62-
63-
if root.left is None and root.right is None:
64-
return None
65-
return root
68+
return None if root.left is None and root.right is None else root
6669
```
6770

6871
### **Java**
6972

7073
```java
74+
/**
75+
* Definition for a binary tree node.
76+
* public class TreeNode {
77+
* int val;
78+
* TreeNode left;
79+
* TreeNode right;
80+
* TreeNode() {}
81+
* TreeNode(int val) { this.val = val; }
82+
* TreeNode(int val, TreeNode left, TreeNode right) {
83+
* this.val = val;
84+
* this.left = left;
85+
* this.right = right;
86+
* }
87+
* }
88+
*/
7189
class Solution {
7290
public TreeNode sufficientSubset(TreeNode root, int limit) {
7391
if (root == null) {
@@ -87,6 +105,14 @@ class Solution {
87105
### **Go**
88106

89107
```go
108+
/**
109+
* Definition for a binary tree node.
110+
* type TreeNode struct {
111+
* Val int
112+
* Left *TreeNode
113+
* Right *TreeNode
114+
* }
115+
*/
90116
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
91117
if root == nil {
92118
return nil
@@ -113,22 +139,57 @@ func sufficientSubset(root *TreeNode, limit int) *TreeNode {
113139
### **C++**
114140

115141
```cpp
142+
/**
143+
* Definition for a binary tree node.
144+
* struct TreeNode {
145+
* int val;
146+
* TreeNode *left;
147+
* TreeNode *right;
148+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
149+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
150+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
151+
* };
152+
*/
116153
class Solution {
117154
public:
118155
TreeNode* sufficientSubset(TreeNode* root, int limit) {
119-
if (root == nullptr) return nullptr;
120-
156+
if (!root) return nullptr;
121157
limit -= root->val;
122-
if (root->left == nullptr && root->right == nullptr)
123-
return limit > 0 ? nullptr : root;
124-
158+
if (!root->left && !root->right) return limit > 0 ? nullptr : root;
125159
root->left = sufficientSubset(root->left, limit);
126160
root->right = sufficientSubset(root->right, limit);
161+
return !root->left && !root->right ? nullptr : root;
162+
}
163+
};
164+
```
127165
128-
if (root->left == nullptr && root->right == nullptr)
129-
return nullptr;
130-
return root;
166+
### **JavaScript**
167+
168+
```js
169+
/**
170+
* Definition for a binary tree node.
171+
* function TreeNode(val, left, right) {
172+
* this.val = (val===undefined ? 0 : val)
173+
* this.left = (left===undefined ? null : left)
174+
* this.right = (right===undefined ? null : right)
175+
* }
176+
*/
177+
/**
178+
* @param {TreeNode} root
179+
* @param {number} limit
180+
* @return {TreeNode}
181+
*/
182+
var sufficientSubset = function(root, limit) {
183+
if (!root) {
184+
return null;
185+
}
186+
limit -= root.val;
187+
if (!root.left && !root.right) {
188+
return limit > 0 ? null : root;
131189
}
190+
root.left = sufficientSubset(root.left, limit);
191+
root.right = sufficientSubset(root.right, limit);
192+
return !root.left && !root.right ? null : root;
132193
};
133194
```
134195

‎solution/1000-1099/1080.Insufficient Nodes in Root to Leaf Paths/Solutioin.go

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,11 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* type TreeNode struct {
4+
* Val int
5+
* Left *TreeNode
6+
* Right *TreeNode
7+
* }
8+
*/
19
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
210
if root == nil {
311
return nil
@@ -18,4 +26,4 @@ func sufficientSubset(root *TreeNode, limit int) *TreeNode {
1826
return nil
1927
}
2028
return root
21-
}
29+
}

‎solution/1000-1099/1080.Insufficient Nodes in Root to Leaf Paths/Solution.cpp

Lines changed: 15 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,22 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* struct TreeNode {
4+
* int val;
5+
* TreeNode *left;
6+
* TreeNode *right;
7+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
8+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10+
* };
11+
*/
112
class Solution {
213
public:
314
TreeNode* sufficientSubset(TreeNode* root, int limit) {
4-
if (root == nullptr) return nullptr;
5-
15+
if (!root) return nullptr;
616
limit -= root->val;
7-
if (root->left == nullptr && root->right == nullptr)
8-
return limit > 0 ? nullptr : root;
9-
17+
if (!root->left && !root->right) return limit > 0 ? nullptr : root;
1018
root->left = sufficientSubset(root->left, limit);
1119
root->right = sufficientSubset(root->right, limit);
12-
13-
if (root->left == nullptr && root->right == nullptr)
14-
return nullptr;
15-
return root;
20+
return !root->left && !root->right ? nullptr : root;
1621
}
17-
};
22+
};

‎solution/1000-1099/1080.Insufficient Nodes in Root to Leaf Paths/Solution.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* function TreeNode(val, left, right) {
4+
* this.val = (val===undefined ? 0 : val)
5+
* this.left = (left===undefined ? null : left)
6+
* this.right = (right===undefined ? null : right)
7+
* }
8+
*/
9+
/**
10+
* @param {TreeNode} root
11+
* @param {number} limit
12+
* @return {TreeNode}
13+
*/
14+
var sufficientSubset = function(root, limit) {
15+
if (!root) {
16+
return null;
17+
}
18+
limit -= root.val;
19+
if (!root.left && !root.right) {
20+
return limit > 0 ? null : root;
21+
}
22+
root.left = sufficientSubset(root.left, limit);
23+
root.right = sufficientSubset(root.right, limit);
24+
return !root.left && !root.right ? null : root;
25+
};

‎solution/1000-1099/1080.Insufficient Nodes in Root to Leaf Paths/Solution.java

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,18 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode() {}
8+
* TreeNode(int val) { this.val = val; }
9+
* TreeNode(int val, TreeNode left, TreeNode right) {
10+
* this.val = val;
11+
* this.left = left;
12+
* this.right = right;
13+
* }
14+
* }
15+
*/
116
class Solution {
217
public TreeNode sufficientSubset(TreeNode root, int limit) {
318
if (root == null) {
@@ -11,4 +26,4 @@ public TreeNode sufficientSubset(TreeNode root, int limit) {
1126
root.right = sufficientSubset(root.right, limit);
1227
return root.left == null && root.right == null ? null : root;
1328
}
14-
}
29+
}

0 commit comments

Comments
 (0)