-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInorder_Successor_in_BST.java
More file actions
38 lines (29 loc) · 1.01 KB
/
Copy pathInorder_Successor_in_BST.java
File metadata and controls
38 lines (29 loc) · 1.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
285. Inorder Successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
//http://www.cnblogs.com/grandyang/p/5306162.html
//https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode succ = null;
while (root != null) {
if (p.val < root.val) {
succ = root;
root = root.left;
}
else
root = root.right;
}
return succ;
}
//////////////////////////////////////////////////////////////
//https://discuss.leetcode.com/topic/25076/share-my-java-recursive-solution
public TreeNode successor(TreeNode root, TreeNode p) {
if (root == null)
return null;
if (root.val <= p.val) {
return successor(root.right, p);
} else {
TreeNode left = successor(root.left, p);
return (left != null) ? left : root;
}
}