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

Commit4344bcd

Browse files
authored
Merge pull request6boris#459 from 0xff-dev/1609
Add solution and test-cases for problem 1609
2 parents66f2bce +b7010e2 commit4344bcd

File tree

6 files changed

+137
-21
lines changed

6 files changed

+137
-21
lines changed

‎leetcode/1601-1700/1609.Even-Odd-Tree/README.md

Lines changed: 37 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,52 @@
11
#[1609.Even Odd Tree][title]
22

3-
>[!WARNING|style:flat]
4-
>This question is temporarily unanswered if you have good ideas. Welcome to[Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
5-
63
##Description
4+
A binary tree is named**Even-Odd** if it meets the following conditions:
5+
6+
- The root of the binary tree is at level index`0`, its children are at level index`1`, their children are at level index`2`, etc.
7+
- For every**even-indexed** level, all nodes at the level have**odd** integer values in**strictly increasing** order (from left to right).
8+
- For every**odd-indexed** level, all nodes at the level have**even** integer values in**strictly decreasing** order (from left to right).
9+
10+
Given the`root` of a binary tree, return`true` if the binary tree is**Even-Odd**, otherwise return`false`.
711

8-
**Example 1:**
12+
**Example 1:**
13+
14+
![example1](./sample_1_1966.png)
915

1016
```
11-
Input: a = "11", b = "1"
12-
Output: "100"
17+
Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
18+
Output: true
19+
Explanation: The node values on each level are:
20+
Level 0: [1]
21+
Level 1: [10,4]
22+
Level 2: [3,7,9]
23+
Level 3: [12,8,6,2]
24+
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.
1325
```
1426

15-
##题意
16-
>...
27+
**Example 2:**
1728

18-
##题解
29+
![example2](./sample_2_1966.png)
1930

20-
###思路1
21-
>...
22-
Even Odd Tree
23-
```go
31+
```
32+
Input: root = [5,4,2,3,3,7]
33+
Output: false
34+
Explanation: The node values on each level are:
35+
Level 0: [5]
36+
Level 1: [4,2]
37+
Level 2: [3,3,7]
38+
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.
2439
```
2540

41+
**Example 3:**
42+
43+
![example3](./sample_1_333_1966.png)
44+
45+
```
46+
Input: root = [5,9,1,3,5,7]
47+
Output: false
48+
Explanation: Node values in the level 1 should be even integers.
49+
```
2650

2751
##结语
2852

Lines changed: 37 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,40 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
typeTreeNodestruct {
4+
Valint
5+
Left,Right*TreeNode
6+
}
7+
8+
funcSolution(root*TreeNode)bool {
9+
ifroot==nil||root.Val&1!=1 {
10+
returnfalse
11+
}
12+
queue:= []*TreeNode{root}
13+
next:=1
14+
forlen(queue)>0 {
15+
nextQ:=make([]*TreeNode,0)
16+
pre:=-1
17+
18+
for_,item:=rangequeue {
19+
ifitem.Left!=nil {
20+
21+
if!((pre==-1&&item.Left.Val&1!=next)|| (next&1==1&&item.Left.Val&1==0&&item.Left.Val<pre)|| (next&1==0&&item.Left.Val&1==1&&item.Left.Val>pre)) {
22+
returnfalse
23+
}
24+
pre=item.Left.Val
25+
nextQ=append(nextQ,item.Left)
26+
}
27+
ifitem.Right!=nil {
28+
if!((pre==-1&&item.Right.Val&1!=next)|| (next&1==1&&item.Right.Val&1==0&&item.Right.Val<pre)|| (next&1==0&&item.Right.Val&1==1&&item.Right.Val>pre)) {
29+
returnfalse
30+
}
31+
pre=item.Right.Val
32+
nextQ=append(nextQ,item.Right)
33+
}
34+
}
35+
36+
next=1-next
37+
queue=nextQ
38+
}
39+
returntrue
540
}

‎leetcode/1601-1700/1609.Even-Odd-Tree/Solution_test.go

Lines changed: 63 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -10,12 +10,69 @@ func TestSolution(t *testing.T) {
1010
//测试用例
1111
cases:= []struct {
1212
namestring
13-
inputsbool
13+
inputs*TreeNode
1414
expectbool
1515
}{
16-
{"TestCase",true,true},
17-
{"TestCase",true,true},
18-
{"TestCase",false,false},
16+
{"TestCase1",&TreeNode{
17+
Val:1,
18+
Left:&TreeNode{
19+
Val:10,
20+
Left:&TreeNode{
21+
Val:3,
22+
Left:&TreeNode{
23+
Val:12,
24+
},
25+
Right:&TreeNode{
26+
Val:8,
27+
},
28+
},
29+
},
30+
Right:&TreeNode{
31+
Val:4,
32+
Left:&TreeNode{
33+
Val:7,
34+
Left:&TreeNode{
35+
Val:6,
36+
},
37+
},
38+
Right:&TreeNode{
39+
Val:9,
40+
Right:&TreeNode{Val:2},
41+
},
42+
},
43+
},true},
44+
{"TestCase2",&TreeNode{
45+
Val:5,
46+
Left:&TreeNode{
47+
Val:4,
48+
Left:&TreeNode{
49+
Val:3,
50+
},
51+
Right:&TreeNode{
52+
Val:3,
53+
},
54+
},
55+
Right:&TreeNode{
56+
Val:2,
57+
Left:&TreeNode{Val:7},
58+
},
59+
},false},
60+
{"TestCase3",&TreeNode{
61+
Val:5,
62+
Left:&TreeNode{
63+
Val:9,
64+
Left:&TreeNode{
65+
Val:3,
66+
},
67+
Right:&TreeNode{
68+
Val:5,
69+
},
70+
},
71+
Right:&TreeNode{
72+
Val:1,
73+
Left:&TreeNode{Val:7},
74+
},
75+
},false},
1976
}
2077

2178
//开始测试
@@ -30,10 +87,10 @@ func TestSolution(t *testing.T) {
3087
}
3188
}
3289

33-
//压力测试
90+
//压力测试
3491
funcBenchmarkSolution(b*testing.B) {
3592
}
3693

37-
//使用案列
94+
//使用案列
3895
funcExampleSolution() {
3996
}
Loading
Loading

0 commit comments

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