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

Commitbbfc235

Browse files
committed
285 (1) iterative & recursive solution
1 parent55f35f9 commitbbfc235

File tree

6 files changed

+367
-17
lines changed

6 files changed

+367
-17
lines changed
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
***************************************************************************
3+
* Description:
4+
*
5+
* Given a binary search tree and a node in it, find the in-order successor
6+
* of that node in the BST.
7+
*
8+
* Note: If the given node has no in-order successor in the tree, return null.
9+
*
10+
***************************************************************************
11+
* @tag : Tree
12+
* {@link https://leetcode.com/problems/inorder-successor-in-bst/ }
13+
*/
14+
package_285_InorderSuccessorInBST;
15+
16+
importcom.leetcode.TreeNode;
17+
18+
/** see test {@link _285_InorderSuccessorInBST.SolutionTest } */
19+
publicclassPractice {
20+
21+
publicTreeNodeinorderSuccessor(TreeNoderoot,TreeNodenode) {
22+
// TODO Auto-generated method stub
23+
returnnull;
24+
}
25+
26+
}

‎src/s08_InorderSuccessorInBST/Solution.javarenamed to‎src/_285_InorderSuccessorInBST/Solution.java

Lines changed: 11 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,28 @@
11
/**
2-
* Time : O(h) ; Space: O(1)
2+
* Time : O() ; Space: O()
33
* @tag : Tree
44
* @by : Steven Cooks
5-
* @date:Aug 11, 2015
5+
* @date:Sep 30, 2015
66
***************************************************************************
77
* Description:
88
*
9-
* Find the successor of given in in-order traversal, i.e. node that has
10-
* next larger number.
9+
* Given a binary search tree and a node in it, find the in-order successor
10+
* of that node in the BST.
11+
*
12+
* Note: If the given node has no in-order successor in the tree, return null.
1113
*
1214
***************************************************************************
13-
* {@link _173_BinarySearchTreeIterator.Solution }
14-
* {@link http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/ }
15+
* {@link https://leetcode.com/problems/inorder-successor-in-bst/ }
1516
*/
16-
packages08_InorderSuccessorInBST;
17+
package_285_InorderSuccessorInBST;
1718

1819
importcom.leetcode.TreeNode;
1920

21+
/** see test {@link _285_InorderSuccessorInBST.SolutionTest } */
2022

2123
publicclassSolution {
22-
23-
/**
24-
* Returns the successor of given node in the binary search tree.
25-
*
26-
* @param root
27-
* @param node
28-
* @return successor node
29-
*/
24+
25+
// iterative version
3026
publicTreeNodeinorderSuccessor(TreeNoderoot,TreeNodenode) {
3127
if (root ==null ||node ==null) {
3228
returnnull;
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* Time : O() ; Space: O()
3+
* @tag : Tree
4+
* @by : Steven Cooks
5+
* @date: Sep 30, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* Given a binary search tree and a node in it, find the in-order successor
10+
* of that node in the BST.
11+
*
12+
* Note: If the given node has no in-order successor in the tree, return null.
13+
*
14+
***************************************************************************
15+
* {@link https://leetcode.com/problems/inorder-successor-in-bst/ }
16+
*/
17+
package_285_InorderSuccessorInBST;
18+
19+
importcom.leetcode.TreeNode;
20+
21+
/** see test {@link _285_InorderSuccessorInBST.SolutionRecursiveTest } */
22+
publicclassSolutionRecursive {
23+
24+
// recursive version
25+
publicTreeNodeinorderSuccessor(TreeNoderoot,TreeNodep) {
26+
if (root ==null ||p ==null) {
27+
returnnull;
28+
}
29+
if (root.val >p.val) {
30+
TreeNodeleft =inorderSuccessor(root.left,p);
31+
if (left !=null) {
32+
returnleft;
33+
}
34+
}
35+
if (p.val <root.val) {
36+
returnroot;
37+
}
38+
returninorderSuccessor(root.right,p);
39+
40+
}
41+
42+
}
Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
package_285_InorderSuccessorInBST;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
importcom.leetcode.TreeNode;
12+
13+
publicclassPracticeTest {
14+
15+
/** Test method for {@link _285_InorderSuccessorInBST.Practice } */
16+
Practicesolution;
17+
18+
@Rule
19+
publicTimeoutglobalTimeout =newTimeout(200);
20+
21+
@Before
22+
publicvoidsetUp()throwsException {
23+
solution =newPractice();
24+
}
25+
26+
@After
27+
publicvoidtearDown()throwsException {
28+
solution =null;
29+
}
30+
31+
// 1
32+
@Test
33+
publicvoidTest1() {
34+
TreeNoderoot =TreeNode.getBST1();
35+
TreeNodenode =root;
36+
TreeNodeactual =solution.inorderSuccessor(root,node);
37+
TreeNodeexpected =null;
38+
assertEquals(expected,actual);
39+
}
40+
41+
// null
42+
@Test
43+
publicvoidTest2() {
44+
TreeNoderoot =null;
45+
TreeNodenode =null;
46+
TreeNodeactual =solution.inorderSuccessor(root,node);
47+
TreeNodeexpected =null;
48+
assertEquals(expected,actual);
49+
}
50+
51+
// 1
52+
// \
53+
// 2
54+
// \
55+
// 3
56+
@Test
57+
publicvoidTest3() {
58+
TreeNoderoot =TreeNode.getBST2();
59+
TreeNodenode =null;
60+
TreeNodeactual =solution.inorderSuccessor(root,node);
61+
TreeNodeexpected =null;
62+
assertEquals(expected,actual);
63+
}
64+
65+
// 1 <- node
66+
// \
67+
// 2
68+
// \
69+
// 3
70+
@Test
71+
publicvoidTest4() {
72+
TreeNoderoot =TreeNode.getBST2();
73+
TreeNodenode =root;
74+
TreeNodeactual =solution.inorderSuccessor(root,node);
75+
TreeNodeexpected =root.right;
76+
assertEquals(expected,actual);
77+
}
78+
79+
// 3
80+
// /
81+
// 2 <- node
82+
// /
83+
// 1
84+
@Test
85+
publicvoidTest5() {
86+
TreeNoderoot =TreeNode.getBST3();
87+
TreeNodenode =root.left;
88+
TreeNodeactual =solution.inorderSuccessor(root,node);
89+
TreeNodeexpected =root;
90+
assertEquals(expected,actual);
91+
}
92+
93+
// 10
94+
// / \
95+
// 5 12
96+
// / \
97+
// 4 7 <-node
98+
@Test
99+
publicvoidTest6() {
100+
TreeNoderoot =TreeNode.getBST5();
101+
TreeNodenode =root.left.right;
102+
TreeNodeactual =solution.inorderSuccessor(root,node);
103+
TreeNodeexpected =root;
104+
assertEquals(expected,actual);
105+
}
106+
107+
// 8
108+
// / \
109+
// 6 18
110+
// / \ / \
111+
// 3 7 10 20
112+
// \ node
113+
// 5
114+
// /
115+
// 4
116+
@Test
117+
publicvoidTest7() {
118+
TreeNoderoot =TreeNode.getBST6();
119+
TreeNodenode =root.right.left;
120+
TreeNodeactual =solution.inorderSuccessor(root,node);
121+
TreeNodeexpected =root.right;
122+
assertEquals(expected,actual);
123+
}
124+
125+
// 8
126+
// / \
127+
// 6 18
128+
// / \ / \
129+
// 3 7 10 20
130+
// \ node
131+
// 5
132+
// /
133+
// 4 <- node
134+
@Test
135+
publicvoidTest8() {
136+
TreeNoderoot =TreeNode.getBST6();
137+
TreeNodenode =root.left.left.right.left;
138+
TreeNodeactual =solution.inorderSuccessor(root,node);
139+
TreeNodeexpected =root.left.left.right;
140+
assertEquals(expected,actual);
141+
}
142+
143+
}

0 commit comments

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