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

Commit9bc71e3

Browse files
add a solution for 222
1 parent768a893 commit9bc71e3

File tree

2 files changed

+110
-0
lines changed

2 files changed

+110
-0
lines changed

‎src/main/java/com/fishercoder/solutions/_222.java

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,4 +37,69 @@ private int getLeftHeight(TreeNode root) {
3737
}
3838
}
3939

40+
publicstaticclassSolution2 {
41+
/**
42+
* credit: https://leetcode.com/problems/count-complete-tree-nodes/solution/
43+
*/
44+
publicintcountNodes(TreeNoderoot) {
45+
if (root ==null) {
46+
return0;
47+
}
48+
intdepth =getDepth(root);
49+
if (depth ==0) {
50+
return1;
51+
}
52+
intleft =0;
53+
intright = (int)Math.pow(2,depth) -1;
54+
//here the condition needs to be not bigger than right, instead of the typical strictly smaller than right.
55+
while (left <=right) {
56+
intmid =left + (right -left) /2;
57+
//this is to suppose the elements on the last level are numbered from 1 to Math.pow(2, d) - 1, we are using
58+
//binary search here to find the right-most number
59+
if (exists(root,mid,depth)) {
60+
left =mid +1;
61+
}else {
62+
right =mid -1;
63+
}
64+
}
65+
//number of all nodes equals all nodes in the previous level + all the nodes on the last level indicated by variable "left"
66+
return (int)Math.pow(2,depth) -1 +left;
67+
}
68+
69+
privatebooleanexists(TreeNoderoot,inttarget,intdepth) {
70+
/**An example complete tree in this algorithm:
71+
* 1
72+
* / \
73+
* 2 3
74+
* / \ /
75+
* 1 2 3 (we use 1, 2, 3 at this level to indicate how this program runs instead of 4, 5, 6)
76+
*
77+
* first, target is 1, we found 1 <= 1 (root), so we go to root.left, after going down to the last level (depth),
78+
* we found this target exists: node != null, we return true from this function
79+
* */
80+
intleft =0;
81+
intright = (int)Math.pow(2,depth) -1;
82+
for (inti =0;i <depth;i++) {
83+
intmid =left + (right -left) /2;
84+
if (target <=mid) {
85+
root =root.left;
86+
right =mid;
87+
}else {
88+
root =root.right;
89+
left =mid +1;
90+
}
91+
}
92+
returnroot !=null;
93+
}
94+
95+
privateintgetDepth(TreeNoderoot) {
96+
intdepth =0;
97+
while (root.left !=null) {
98+
root =root.left;
99+
depth++;
100+
}
101+
returndepth;
102+
}
103+
}
104+
40105
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.common.classes.TreeNode;
4+
importcom.fishercoder.common.utils.CommonUtils;
5+
importcom.fishercoder.common.utils.TreeUtils;
6+
importcom.fishercoder.solutions._2007;
7+
importcom.fishercoder.solutions._222;
8+
importorg.junit.BeforeClass;
9+
importorg.junit.Test;
10+
11+
importjava.util.Arrays;
12+
13+
importstaticorg.junit.Assert.assertEquals;
14+
15+
publicclass_222Test {
16+
privatestatic_222.Solution1solution1;
17+
privatestatic_222.Solution2solution2;
18+
privatestaticintexpected;
19+
privatestaticTreeNoderoot;
20+
21+
@BeforeClass
22+
publicstaticvoidsetup() {
23+
solution1 =new_222.Solution1();
24+
solution2 =new_222.Solution2();
25+
}
26+
27+
@Test
28+
publicvoidtest1() {
29+
root =TreeUtils.constructBinaryTree(Arrays.asList(1,2,3));
30+
TreeUtils.printBinaryTree(root);
31+
expected =3;
32+
assertEquals(expected,solution1.countNodes(root));
33+
assertEquals(expected,solution2.countNodes(root));
34+
}
35+
36+
@Test
37+
publicvoidtest2() {
38+
root =TreeUtils.constructBinaryTree(Arrays.asList(1,2,3,4,5,6));
39+
TreeUtils.printBinaryTree(root);
40+
expected =6;
41+
assertEquals(expected,solution1.countNodes(root));
42+
assertEquals(expected,solution2.countNodes(root));
43+
}
44+
45+
}

0 commit comments

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