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

Commit8daa7f1

Browse files
add articles (#5101)
* add binary-tree-longest-consecutive-sequence.md article* add binary-tree-longest-consecutive-sequence-ii.md article* add count-univalue-subtrees.md article* add maximum-average-subtree.md article* add boundary-of-binary-tree.md article* add find-leaves-of-binary-tree.md article* add closest-binary-search-tree-value.md article* add closest-binary-search-tree-value-ii.md article* add verify-preorder-sequence-in-binary-search-tree.md* add two-sum-bsts.md article* add largest-bst-subtree.md article* add clone-n-ary-tree.md article* add find-root-of-n-ary-tree.md article* add diameter-of-n-ary-tree.md article* add find-the-celebrity.md article
1 parentb76b800 commit8daa7f1

15 files changed

+5266
-0
lines changed
Lines changed: 190 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,190 @@
1+
##1. Brute Force (Time Limit Exceeded)
2+
3+
###Time & Space Complexity
4+
5+
- Time complexity: $O(n^3)$
6+
- Space complexity: $O(n^3)$
7+
8+
> Where $n$ is the number of nodes in the input tree
9+
10+
---
11+
12+
##2. Single traversal
13+
14+
::tabs-start
15+
16+
```python
17+
classSolution:
18+
deflongestConsecutive(self,root: TreeNode) ->int:
19+
20+
deflongest_path(root: TreeNode) -> List[int]:
21+
nonlocal maxval
22+
23+
ifnot root:
24+
return [0,0]
25+
26+
inr= dcr=1
27+
if root.left:
28+
left= longest_path(root.left)
29+
if (root.val== root.left.val+1):
30+
dcr= left[1]+1
31+
elif (root.val== root.left.val-1):
32+
inr= left[0]+1
33+
34+
if root.right:
35+
right= longest_path(root.right)
36+
if (root.val== root.right.val+1):
37+
dcr=max(dcr, right[1]+1)
38+
elif (root.val== root.right.val-1):
39+
inr=max(inr, right[0]+1)
40+
41+
maxval=max(maxval, dcr+ inr-1)
42+
return [inr, dcr]
43+
44+
maxval=0
45+
longest_path(root)
46+
return maxval
47+
```
48+
49+
```java
50+
classSolution {
51+
int maxval=0;
52+
53+
publicintlongestConsecutive(TreeNoderoot) {
54+
longestPath(root);
55+
return maxval;
56+
}
57+
58+
publicint[]longestPath(TreeNoderoot) {
59+
if (root==null) {
60+
returnnewint[] {0,0};
61+
}
62+
63+
int inr=1, dcr=1;
64+
if (root.left!=null) {
65+
int[] left= longestPath(root.left);
66+
if (root.val== root.left.val+1) {
67+
dcr= left[1]+1;
68+
}elseif (root.val== root.left.val-1) {
69+
inr= left[0]+1;
70+
}
71+
}
72+
73+
if (root.right!=null) {
74+
int[] right= longestPath(root.right);
75+
if (root.val== root.right.val+1) {
76+
dcr=Math.max(dcr, right[1]+1);
77+
}elseif (root.val== root.right.val-1) {
78+
inr=Math.max(inr, right[0]+1);
79+
}
80+
}
81+
82+
maxval=Math.max(maxval, dcr+ inr-1);
83+
returnnewint[] {inr, dcr};
84+
}
85+
}
86+
```
87+
88+
```cpp
89+
classSolution {
90+
private:
91+
int maxval = 0;
92+
93+
vector<int> longestPath(TreeNode* root) {
94+
if (root == nullptr) {
95+
return {0, 0};
96+
}
97+
98+
int inr = 1, dcr = 1;
99+
100+
if (root->left != nullptr) {
101+
vector<int> left = longestPath(root->left);
102+
if (root->val == root->left->val + 1) {
103+
dcr = left[1] + 1;
104+
} else if (root->val == root->left->val - 1) {
105+
inr = left[0] + 1;
106+
}
107+
}
108+
109+
if (root->right != nullptr) {
110+
vector<int> right = longestPath(root->right);
111+
if (root->val == root->right->val + 1) {
112+
dcr = max(dcr, right[1] + 1);
113+
} else if (root->val == root->right->val - 1) {
114+
inr = max(inr, right[0] + 1);
115+
}
116+
}
117+
118+
maxval = max(maxval, dcr + inr - 1);
119+
120+
return {inr, dcr};
121+
}
122+
123+
public:
124+
int longestConsecutive(TreeNode* root) {
125+
longestPath(root);
126+
return maxval;
127+
}
128+
};
129+
```
130+
131+
```javascript
132+
class Solution {
133+
constructor() {
134+
this.maxval = 0;
135+
}
136+
137+
/**
138+
* @param {TreeNode} root
139+
* @return {number}
140+
*/
141+
longestConsecutive(root) {
142+
this.maxval = 0;
143+
this.longestPath(root);
144+
return this.maxval;
145+
}
146+
147+
/**
148+
* @param {TreeNode} root
149+
* @return {number[]}
150+
*/
151+
longestPath(root) {
152+
if (root === null) {
153+
return [0, 0];
154+
}
155+
156+
let inr = 1, dcr = 1;
157+
158+
if (root.left !== null) {
159+
let left = this.longestPath(root.left);
160+
if (root.val === root.left.val + 1) {
161+
dcr = left[1] + 1;
162+
} else if (root.val === root.left.val - 1) {
163+
inr = left[0] + 1;
164+
}
165+
}
166+
167+
if (root.right !== null) {
168+
let right = this.longestPath(root.right);
169+
if (root.val === root.right.val + 1) {
170+
dcr = Math.max(dcr, right[1] + 1);
171+
} else if (root.val === root.right.val - 1) {
172+
inr = Math.max(inr, right[0] + 1);
173+
}
174+
}
175+
176+
this.maxval = Math.max(this.maxval, dcr + inr - 1);
177+
178+
return [inr, dcr];
179+
}
180+
}
181+
```
182+
183+
::tabs-end
184+
185+
###Time & Space Complexity
186+
187+
- Time complexity: $O(n)$
188+
- Space complexity: $O(n)$
189+
190+
> Where $n$ is the number of nodes in the input tree

0 commit comments

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