import java.util.HashSet;
import java.util.Set;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
}
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
return helper(root,p.val,new HashSet<TreeNode>());
}
public TreeNode helper(TreeNode root, int val, Set<TreeNode> set){
if(root == null)return null;
set.add(root);
TreeNode res = null;
if(root.val <= val){
if(root.right != null && !set.contains(root.right)){
res = helper(root.right,val,set);
}
if(res != null)return res;
return helper(root.parent,val,set);
} else {
return root;
}
}
}
import java.util.HashSet;
import java.util.Set;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
class TreeNode{
TreeNode left;
TreeNode right;
TreeNode parent;
}
public TreeNode inorderSuccessor(TreeNode p) {
if(p.right != null)return p.right;
while(p.parent != null){
if(p.parent.right == p)p = p.parent;
else return p.parent;
}
return null;
}
}
