22
33import com .fishercoder .common .classes .TreeNode ;
44
5+ import java .util .ArrayList ;
56import java .util .Iterator ;
7+ import java .util .List ;
68import java .util .Map ;
79import java .util .TreeMap ;
810
@@ -17,7 +19,7 @@ public static class Solution1 {
1719 * <p>
1820 * The time complexity should be O(h) where h is the depth of the result node.
1921 * succ is a pointer that keeps the possible successor.
20- * Whenever you go left the current root is the new possible successor, otherwisethe it remains the same.
22+ * Whenever you go left the current root is the new possible successor, otherwise it remains the same.
2123 * <p>
2224 * Only in a balanced BST O(h) = O(log n). In the worst case h can be as large as n.
2325 */
@@ -64,4 +66,31 @@ private void inorderTraversal(TreeNode root, TreeMap<Integer, TreeNode> map) {
6466 }
6567 }
6668
69+ public static class Solution3 {
70+ public TreeNode inorderSuccessor (TreeNode root ,TreeNode p ) {
71+ List <TreeNode >inorder =new ArrayList <>();
72+ dfs (root ,inorder );
73+ for (int i =0 ;i <inorder .size () -1 ;i ++) {
74+ if (inorder .get (i ) ==p ) {
75+ return inorder .get (i +1 );
76+ }
77+ }
78+ return null ;
79+ }
80+
81+ private List <TreeNode >dfs (TreeNode root ,List <TreeNode >inorder ) {
82+ if (root ==null ) {
83+ return inorder ;
84+ }
85+ if (root .left !=null ) {
86+ dfs (root .left ,inorder );
87+ }
88+ inorder .add (root );
89+ if (root .right !=null ) {
90+ dfs (root .right ,inorder );
91+ }
92+ return inorder ;
93+ }
94+ }
95+
6796}