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

Commit9014b37

Browse files
authored
Merge pull requestneetcode-gh#3674 from Srihari2222/develop_articles
Sri Hari: Batch-2/Neetcode-150/articles
2 parents476aaaf +77ccc65 commit9014b37

8 files changed

+3690
-0
lines changed

‎articles/balanced-binary-tree.md

Lines changed: 616 additions & 0 deletions
Large diffs are not rendered by default.
Lines changed: 398 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,398 @@
1+
##1. Depth First Search
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+
13+
classSolution:
14+
defrightSideView(self,root: Optional[TreeNode]) -> List[int]:
15+
res= []
16+
17+
defdfs(node,depth):
18+
ifnot node:
19+
returnNone
20+
if depth==len(res):
21+
res.append(node.val)
22+
23+
dfs(node.right, depth+1)
24+
dfs(node.left, depth+1)
25+
26+
dfs(root,0)
27+
return res
28+
```
29+
30+
```java
31+
/**
32+
* Definition for a binary tree node.
33+
* public class TreeNode {
34+
* int val;
35+
* TreeNode left;
36+
* TreeNode right;
37+
* TreeNode() {}
38+
* TreeNode(int val) { this.val = val; }
39+
* TreeNode(int val, TreeNode left, TreeNode right) {
40+
* this.val = val;
41+
* this.left = left;
42+
* this.right = right;
43+
* }
44+
* }
45+
*/
46+
47+
publicclassSolution {
48+
List<Integer> res=newArrayList<>();
49+
50+
publicList<Integer>rightSideView(TreeNoderoot) {
51+
dfs(root,0);
52+
return res;
53+
}
54+
55+
privatevoiddfs(TreeNodenode,intdepth) {
56+
if (node==null) {
57+
return;
58+
}
59+
60+
if (res.size()== depth) {
61+
res.add(node.val);
62+
}
63+
64+
dfs(node.right, depth+1);
65+
dfs(node.left, depth+1);
66+
}
67+
}
68+
```
69+
70+
```cpp
71+
/**
72+
* Definition for a binary tree node.
73+
* struct TreeNode {
74+
* int val;
75+
* TreeNode *left;
76+
* TreeNode *right;
77+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
78+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
79+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
80+
* };
81+
*/
82+
83+
classSolution {
84+
public:
85+
vector<int> res;
86+
87+
vector<int> rightSideView(TreeNode* root) {
88+
dfs(root, 0);
89+
return res;
90+
}
91+
92+
void dfs(TreeNode* node, int depth) {
93+
if (!node) return;
94+
95+
if (res.size() == depth) {
96+
res.push_back(node->val);
97+
}
98+
99+
dfs(node->right, depth + 1);
100+
dfs(node->left, depth + 1);
101+
}
102+
};
103+
```
104+
105+
```javascript
106+
/**
107+
* Definition for a binary tree node.
108+
* class TreeNode {
109+
* constructor(val = 0, left = null, right = null) {
110+
* this.val = val;
111+
* this.left = left;
112+
* this.right = right;
113+
* }
114+
* }
115+
*/
116+
117+
class Solution {
118+
/**
119+
* @param {TreeNode} root
120+
* @return {number[]}
121+
*/
122+
rightSideView(root) {
123+
let res = [];
124+
125+
function dfs(node, depth) {
126+
if (!node) return;
127+
128+
if (res.length === depth) {
129+
res.push(node.val);
130+
}
131+
132+
dfs(node.right, depth + 1);
133+
dfs(node.left, depth + 1);
134+
}
135+
136+
dfs(root, 0);
137+
return res;
138+
}
139+
}
140+
```
141+
142+
```csharp
143+
/**
144+
* Definition for a binary tree node.
145+
* public class TreeNode {
146+
* public int val;
147+
* public TreeNode left;
148+
* public TreeNode right;
149+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
150+
* this.val = val;
151+
* this.left = left;
152+
* this.right = right;
153+
* }
154+
* }
155+
*/
156+
157+
publicclassSolution {
158+
List<int>res=newList<int>();
159+
160+
publicList<int>RightSideView(TreeNoderoot) {
161+
dfs(root,0);
162+
returnres;
163+
}
164+
165+
privatevoiddfs(TreeNodenode,intdepth) {
166+
if (node==null) {
167+
return;
168+
}
169+
170+
if (res.Count==depth) {
171+
res.Add(node.val);
172+
}
173+
174+
dfs(node.right,depth+1);
175+
dfs(node.left,depth+1);
176+
}
177+
}
178+
```
179+
180+
::tabs-end
181+
182+
###Time & Space Complexity
183+
184+
* Time complexity: $O(n)$
185+
* Space complexity: $O(n)$
186+
187+
---
188+
189+
##2. Breadth First Search
190+
191+
::tabs-start
192+
193+
```python
194+
# Definition for a binary tree node.
195+
# class TreeNode:
196+
# def __init__(self, val=0, left=None, right=None):
197+
# self.val = val
198+
# self.left = left
199+
# self.right = right
200+
201+
classSolution:
202+
defrightSideView(self,root: Optional[TreeNode]) -> List[int]:
203+
res= []
204+
q= deque([root])
205+
206+
while q:
207+
rightSide=None
208+
qLen=len(q)
209+
210+
for iinrange(qLen):
211+
node= q.popleft()
212+
if node:
213+
rightSide= node
214+
q.append(node.left)
215+
q.append(node.right)
216+
if rightSide:
217+
res.append(rightSide.val)
218+
return res
219+
```
220+
221+
```java
222+
/**
223+
* Definition for a binary tree node.
224+
* public class TreeNode {
225+
* int val;
226+
* TreeNode left;
227+
* TreeNode right;
228+
* TreeNode() {}
229+
* TreeNode(int val) { this.val = val; }
230+
* TreeNode(int val, TreeNode left, TreeNode right) {
231+
* this.val = val;
232+
* this.left = left;
233+
* this.right = right;
234+
* }
235+
* }
236+
*/
237+
238+
classSolution {
239+
publicList<Integer>rightSideView(TreeNoderoot) {
240+
List<Integer> res=newArrayList<>();
241+
Queue<TreeNode> q=newLinkedList<>();
242+
q.offer(root);
243+
244+
while (!q.isEmpty()) {
245+
TreeNode rightSide=null;
246+
int qLen= q.size();
247+
248+
for (int i=0; i< qLen; i++) {
249+
TreeNode node= q.poll();
250+
if (node!=null) {
251+
rightSide= node;
252+
q.offer(node.left);
253+
q.offer(node.right);
254+
}
255+
}
256+
if (rightSide!=null) {
257+
res.add(rightSide.val);
258+
}
259+
}
260+
return res;
261+
}
262+
}
263+
```
264+
265+
```cpp
266+
/**
267+
* Definition for a binary tree node.
268+
* struct TreeNode {
269+
* int val;
270+
* TreeNode *left;
271+
* TreeNode *right;
272+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
273+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
274+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
275+
* };
276+
*/
277+
278+
classSolution {
279+
public:
280+
vector<int> rightSideView(TreeNode* root) {
281+
vector<int> res;
282+
queue<TreeNode*> q;
283+
q.push(root);
284+
285+
while (!q.empty()) {
286+
TreeNode* rightSide = nullptr;
287+
int qLen = q.size();
288+
289+
for (int i = 0; i < qLen; i++) {
290+
TreeNode* node = q.front();
291+
q.pop();
292+
if (node) {
293+
rightSide = node;
294+
q.push(node->left);
295+
q.push(node->right);
296+
}
297+
}
298+
if (rightSide) {
299+
res.push_back(rightSide->val);
300+
}
301+
}
302+
return res;
303+
}
304+
};
305+
```
306+
307+
```javascript
308+
/**
309+
* Definition for a binary tree node.
310+
* class TreeNode {
311+
* constructor(val = 0, left = null, right = null) {
312+
* this.val = val;
313+
* this.left = left;
314+
* this.right = right;
315+
* }
316+
* }
317+
*/
318+
319+
classSolution {
320+
/**
321+
*@param{TreeNode}root
322+
*@return{number[]}
323+
*/
324+
rightSideView(root) {
325+
constres= [];
326+
constq=newQueue();
327+
328+
q.push(root);
329+
330+
while (!q.isEmpty()) {
331+
let rightSide=null;
332+
constqLen=q.size();
333+
334+
for (let i=0; i< qLen; i++) {
335+
constnode=q.pop();
336+
if (node) {
337+
rightSide= node;
338+
q.push(node.left);
339+
q.push(node.right);
340+
}
341+
}
342+
if (rightSide) {
343+
res.push(rightSide.val);
344+
}
345+
}
346+
return res;
347+
}
348+
}
349+
```
350+
351+
```csharp
352+
/**
353+
* Definition for a binary tree node.
354+
* public class TreeNode {
355+
* public int val;
356+
* public TreeNode left;
357+
* public TreeNode right;
358+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
359+
* this.val = val;
360+
* this.left = left;
361+
* this.right = right;
362+
* }
363+
* }
364+
*/
365+
366+
publicclassSolution {
367+
publicList<int>RightSideView(TreeNoderoot) {
368+
List<int>res=newList<int>();
369+
Queue<TreeNode>q=newQueue<TreeNode>();
370+
q.Enqueue(root);
371+
372+
while (q.Count>0) {
373+
TreeNoderightSide=null;
374+
intqLen=q.Count;
375+
376+
for (inti=0;i<qLen;i++) {
377+
TreeNodenode=q.Dequeue();
378+
if (node!=null) {
379+
rightSide=node;
380+
q.Enqueue(node.left);
381+
q.Enqueue(node.right);
382+
}
383+
}
384+
if (rightSide!=null) {
385+
res.Add(rightSide.val);
386+
}
387+
}
388+
returnres;
389+
}
390+
}
391+
```
392+
393+
::tabs-end
394+
395+
###Time & Space Complexity
396+
397+
* Time complexity: $O(n)$
398+
* Space complexity: $O(n)$

0 commit comments

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