My Accepted Java O(lgN) Iterative Solution


  • 0
    W
    The basic idea is using a stack to store the path and finding the target node p. When find p,there are basically 3 cases:
    
    1. If p has a right subtree, then just find the first left child of this subtree. 
    2. If p is the left child of its parent, then just return its parent
    3. If p is the right child, the just track back the tree until find a node that meets requirement of 1. or 2.    
    
    
    
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
                    if(root==null || root.left==null && root.right==null || p==null) return null;
                    Stack<TreeNode> stack=new Stack<TreeNode>();
                    TreeNode node=root;
                    while(node!=p){
                        stack.push(node);
                        if(p.val<=node.val && node.left!=null) node=node.left;
                        else if(p.val>node.val && node.right!=null) node=node.right;
                        else return null;
                    }
                    TreeNode visitedRight=null;
                    while(!stack.isEmpty() && stack.peek().right==node && node.right==visitedRight){
                        visitedRight=node;
                        node=stack.pop();
                    }
                    if(stack.isEmpty() && node.right==visitedRight) return null;
                    if(node.right==visitedRight) return stack.peek();
                    node=node.right;
                    while(node.left!=null)
                        node=node.left;
                    return node;
                }

  • 0
    Y

    Actually, when you iterate to left, you store the node, if you iterate to right, just do not push this node to the stack. When it is the right child (not right subtree case), you just pop the last node from stack and it is done.


  • 0
    W

    Hi, @yucheyang2, thanks for the comment! I didn't quite get your point. would you mind post some part of your code so that we can understand it?


  • -1

    O(lgN) is impossible. The desired node might be at depth N (I'm assuming with N you mean the number of nodes).


  • 0
    Y
        List<TreeNode> stack = new ArrayList<>();
        TreeNode node = root;
        while (true) {
            if (target < node.val) {
                stack.add(node);
                node = node.left;
            } else if (target > node.val) {
                // stack.add(node);
                node = node.right;
            } else {
                if (node.right == null) {
                    // Your case one and case two can combined to this.
                    if (stack.isEmpty()) {
                       return null;
                    } else {
                        return stack.remove(stack.size() - 1);
                    }
                } else {
                    // Right Sub Tree Case
                    node = node.right;
                    while (node.left != null) {
                        node = node.left;
                    }
                    return node;
                }
            }
        }

  • 0
    C

    His n should mean the total number of nodes. So the height is just kind of lgN


  • 0

    "So the height is just kind of lgN"

    No, height can be up to N.


  • 0
    C

    well, you are right, it's not self-balanced.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.