JAVA 4ms Plain Solution


  • 0
    G

    The p'next node can only come from the p's right child part or the first former node that goes left.

    public class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root == null || p == null) {
                return null;
            }
            if (p.right != null) {
                TreeNode ret = p.right;
                while(ret.left != null) {
                    ret = ret.left;
                }
                return ret;
            }
            TreeNode prev = null;
            TreeNode cur = root;
            while (cur.val != p.val) {
                if (p.val < cur.val) {
                    prev = cur;
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }
            return prev;
        }
    }
    

Log in to reply
 

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