|
2 | 2 |
|
3 | 3 | importcom.fishercoder.common.classes.TreeNode; |
4 | 4 |
|
| 5 | +importjava.util.Iterator; |
| 6 | +importjava.util.Map; |
| 7 | +importjava.util.TreeMap; |
| 8 | + |
5 | 9 | /**285. Inorder Successor in BST |
6 | 10 |
|
7 | 11 | Given a binary search tree and a node in it, find the in-order successor of that node in the BST. |
8 | 12 |
|
9 | 13 | Note: If the given node has no in-order successor in the tree, return null. */ |
10 | 14 | publicclass_285 { |
11 | 15 |
|
12 | | -/**credit: https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative |
13 | | - The inorder traversal of a BST is the nodes in ascending order. |
14 | | - To find a successor, you just need to find the smallest one that is larger than the given value since there are no duplicate values in a BST. |
15 | | - It's just like the binary search in a sorted list. |
16 | | -
|
17 | | - The time complexity should be O(h) where h is the depth of the result node. |
18 | | - succ is a pointer that keeps the possible successor. |
19 | | - Whenever you go left the current root is the new possible successor, otherwise the it remains the same. |
20 | | -
|
21 | | - Only in a balanced BST O(h) = O(log n). In the worst case h can be as large as n. |
22 | | - */ |
23 | | -publicTreeNodeinorderSuccessor(TreeNoderoot,TreeNodep) { |
24 | | -TreeNodesuccessor =null; |
25 | | -while (root !=null) { |
26 | | -if (p.val <root.val) { |
27 | | -successor =root; |
28 | | -root =root.left; |
29 | | - }else { |
30 | | -root =root.right; |
| 16 | +publicstaticclassSolution1 { |
| 17 | +/** |
| 18 | + * credit: https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative |
| 19 | + * The inorder traversal of a BST is the nodes in ascending order. |
| 20 | + * To find a successor, you just need to find the smallest one that is larger than the given value since there are no duplicate values in a BST. |
| 21 | + * It's just like the binary search in a sorted list. |
| 22 | + * <p> |
| 23 | + * The time complexity should be O(h) where h is the depth of the result node. |
| 24 | + * succ is a pointer that keeps the possible successor. |
| 25 | + * Whenever you go left the current root is the new possible successor, otherwise the it remains the same. |
| 26 | + * <p> |
| 27 | + * Only in a balanced BST O(h) = O(log n). In the worst case h can be as large as n. |
| 28 | + */ |
| 29 | +publicTreeNodeinorderSuccessor(TreeNoderoot,TreeNodep) { |
| 30 | +TreeNodesuccessor =null; |
| 31 | +while (root !=null) { |
| 32 | +if (p.val <root.val) { |
| 33 | +successor =root; |
| 34 | +root =root.left; |
| 35 | + }else { |
| 36 | +root =root.right; |
| 37 | + } |
| 38 | + } |
| 39 | +returnsuccessor; |
| 40 | + } |
| 41 | + } |
| 42 | + |
| 43 | +publicstaticclassSolution2 { |
| 44 | +publicTreeNodeinorderSuccessor(TreeNoderoot,TreeNodep) { |
| 45 | +TreeMap<Integer,TreeNode>map =newTreeMap<>(); |
| 46 | +inorderTraversal(root,map); |
| 47 | +Iterator<Map.Entry<Integer,TreeNode>>iterator =map.entrySet().iterator(); |
| 48 | +while (iterator.hasNext()) { |
| 49 | +Map.Entry<Integer,TreeNode>entry =iterator.next(); |
| 50 | +if (entry.getValue() ==p) { |
| 51 | +if (iterator.hasNext()) { |
| 52 | +returniterator.next().getValue(); |
| 53 | + }else { |
| 54 | +returnnull; |
| 55 | + } |
| 56 | + } |
| 57 | + } |
| 58 | +returnnull; |
| 59 | + } |
| 60 | + |
| 61 | +privatevoidinorderTraversal(TreeNoderoot,TreeMap<Integer,TreeNode>map) { |
| 62 | +if (root ==null) { |
| 63 | +return; |
31 | 64 | } |
| 65 | +inorderTraversal(root.left,map); |
| 66 | +map.put(root.val,root); |
| 67 | +inorderTraversal(root.right,map); |
| 68 | +return; |
32 | 69 | } |
33 | | -returnsuccessor; |
34 | 70 | } |
35 | 71 |
|
36 | 72 | } |