Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit03352fe

Browse files
authored
Sri Hari: Batch-5/Neetcode-250/Added-articles (neetcode-gh#3791)
* Batch-5/Neetcode-250/Added-articles* Batch-5/Neetcode-250/Added-articles
1 parente521827 commit03352fe

9 files changed

+5263
-0
lines changed

‎articles/binary-tree-inorder-traversal.md

Lines changed: 467 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/binary-tree-postorder-traversal.md

Lines changed: 662 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/binary-tree-preorder-traversal.md

Lines changed: 468 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/construct-quad-tree.md

Lines changed: 733 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/delete-leaves-with-a-given-value.md

Lines changed: 577 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/delete-node-in-a-bst.md

Lines changed: 632 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/house-robber-iii.md

Lines changed: 457 additions & 0 deletions
Large diffs are not rendered by default.
Lines changed: 292 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,292 @@
1+
##1. Recursion
2+
3+
::tabs-start
4+
5+
```python
6+
# Definition for a binary tree node.
7+
# class TreeNode:
8+
# def __init__(self, val=0, left=None, right=None):
9+
# self.val = val
10+
# self.left = left
11+
# self.right = right
12+
classSolution:
13+
definsertIntoBST(self,root: Optional[TreeNode],val:int) -> Optional[TreeNode]:
14+
ifnot root:
15+
return TreeNode(val)
16+
17+
if val> root.val:
18+
root.right=self.insertIntoBST(root.right, val)
19+
else:
20+
root.left=self.insertIntoBST(root.left, val)
21+
22+
return root
23+
```
24+
25+
```java
26+
/**
27+
* Definition for a binary tree node.
28+
* public class TreeNode {
29+
* int val;
30+
* TreeNode left;
31+
* TreeNode right;
32+
* TreeNode() {}
33+
* TreeNode(int val) { this.val = val; }
34+
* TreeNode(int val, TreeNode left, TreeNode right) {
35+
* this.val = val;
36+
* this.left = left;
37+
* this.right = right;
38+
* }
39+
* }
40+
*/
41+
publicclassSolution {
42+
publicTreeNodeinsertIntoBST(TreeNoderoot,intval) {
43+
if (root==null) {
44+
returnnewTreeNode(val);
45+
}
46+
47+
if (val> root.val) {
48+
root.right= insertIntoBST(root.right, val);
49+
}else {
50+
root.left= insertIntoBST(root.left, val);
51+
}
52+
53+
return root;
54+
}
55+
}
56+
```
57+
58+
```cpp
59+
/**
60+
* Definition for a binary tree node.
61+
* struct TreeNode {
62+
* int val;
63+
* TreeNode *left;
64+
* TreeNode *right;
65+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
66+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
67+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
68+
* };
69+
*/
70+
classSolution {
71+
public:
72+
TreeNode* insertIntoBST(TreeNode* root, int val) {
73+
if (!root) {
74+
return new TreeNode(val);
75+
}
76+
77+
if (val > root->val) {
78+
root->right = insertIntoBST(root->right, val);
79+
} else {
80+
root->left = insertIntoBST(root->left, val);
81+
}
82+
83+
return root;
84+
}
85+
};
86+
```
87+
88+
```javascript
89+
/**
90+
* Definition for a binary tree node.
91+
* class TreeNode {
92+
* constructor(val = 0, left = null, right = null) {
93+
* this.val = val;
94+
* this.left = left;
95+
* this.right = right;
96+
* }
97+
* }
98+
*/
99+
classSolution {
100+
/**
101+
*@param{TreeNode}root
102+
*@param{number}val
103+
*@return{TreeNode}
104+
*/
105+
insertIntoBST(root,val) {
106+
if (!root) {
107+
returnnewTreeNode(val);
108+
}
109+
110+
if (val>root.val) {
111+
root.right=this.insertIntoBST(root.right, val);
112+
}else {
113+
root.left=this.insertIntoBST(root.left, val);
114+
}
115+
116+
return root;
117+
}
118+
}
119+
```
120+
121+
::tabs-end
122+
123+
###Time & Space Complexity
124+
125+
* Time complexity: $O(h)$
126+
* Space complexity: $O(h)$ for the recursion stack.
127+
128+
>Where $h$ is the height of the given binary search tree.
129+
130+
---
131+
132+
##2. Iteration
133+
134+
::tabs-start
135+
136+
```python
137+
# Definition for a binary tree node.
138+
# class TreeNode:
139+
# def __init__(self, val=0, left=None, right=None):
140+
# self.val = val
141+
# self.left = left
142+
# self.right = right
143+
classSolution:
144+
definsertIntoBST(self,root: Optional[TreeNode],val:int) -> Optional[TreeNode]:
145+
ifnot root:
146+
return TreeNode(val)
147+
148+
cur= root
149+
whileTrue:
150+
if val> cur.val:
151+
ifnot cur.right:
152+
cur.right= TreeNode(val)
153+
return root
154+
cur= cur.right
155+
else:
156+
ifnot cur.left:
157+
cur.left= TreeNode(val)
158+
return root
159+
cur= cur.left
160+
```
161+
162+
```java
163+
/**
164+
* Definition for a binary tree node.
165+
* public class TreeNode {
166+
* int val;
167+
* TreeNode left;
168+
* TreeNode right;
169+
* TreeNode() {}
170+
* TreeNode(int val) { this.val = val; }
171+
* TreeNode(int val, TreeNode left, TreeNode right) {
172+
* this.val = val;
173+
* this.left = left;
174+
* this.right = right;
175+
* }
176+
* }
177+
*/
178+
publicclassSolution {
179+
publicTreeNodeinsertIntoBST(TreeNoderoot,intval) {
180+
if (root==null) {
181+
returnnewTreeNode(val);
182+
}
183+
184+
TreeNode cur= root;
185+
while (true) {
186+
if (val> cur.val) {
187+
if (cur.right==null) {
188+
cur.right=newTreeNode(val);
189+
return root;
190+
}
191+
cur= cur.right;
192+
}else {
193+
if (cur.left==null) {
194+
cur.left=newTreeNode(val);
195+
return root;
196+
}
197+
cur= cur.left;
198+
}
199+
}
200+
}
201+
}
202+
```
203+
204+
```cpp
205+
/**
206+
* Definition for a binary tree node.
207+
* struct TreeNode {
208+
* int val;
209+
* TreeNode *left;
210+
* TreeNode *right;
211+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
212+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
213+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
214+
* };
215+
*/
216+
classSolution {
217+
public:
218+
TreeNode* insertIntoBST(TreeNode* root, int val) {
219+
if (!root) {
220+
return new TreeNode(val);
221+
}
222+
223+
TreeNode* cur = root;
224+
while (true) {
225+
if (val > cur->val) {
226+
if (!cur->right) {
227+
cur->right = new TreeNode(val);
228+
return root;
229+
}
230+
cur = cur->right;
231+
}else {
232+
if (!cur->left) {
233+
cur->left = new TreeNode(val);
234+
return root;
235+
}
236+
cur = cur->left;
237+
}
238+
}
239+
}
240+
};
241+
```
242+
243+
```javascript
244+
/**
245+
* Definition for a binary tree node.
246+
* class TreeNode {
247+
* constructor(val = 0, left = null, right = null) {
248+
* this.val = val;
249+
* this.left = left;
250+
* this.right = right;
251+
* }
252+
* }
253+
*/
254+
classSolution {
255+
/**
256+
*@param{TreeNode}root
257+
*@param{number}val
258+
*@return{TreeNode}
259+
*/
260+
insertIntoBST(root,val) {
261+
if (!root) {
262+
returnnewTreeNode(val);
263+
}
264+
265+
let cur= root;
266+
while (true) {
267+
if (val>cur.val) {
268+
if (!cur.right) {
269+
cur.right=newTreeNode(val);
270+
return root;
271+
}
272+
cur=cur.right;
273+
}else {
274+
if (!cur.left) {
275+
cur.left=newTreeNode(val);
276+
return root;
277+
}
278+
cur=cur.left;
279+
}
280+
}
281+
}
282+
}
283+
```
284+
285+
::tabs-end
286+
287+
###Time & Space Complexity
288+
289+
* Time complexity: $O(h)$
290+
* Space complexity: $O(1)$ extra space.
291+
292+
>Where $h$ is the height of the given binary search tree.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp