Java with findMin in right subtree first, then do searching


  • 0
    Z

    Similar to some people's thought, just to show my version.

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root == null) return null;
            if (p.right != null) {
                return findMin(p.right);
            }
            TreeNode succ = null;
            while (root != null) {
                if (root.val < p.val) {
                    root = root.right;
                } else if (root.val > p.val) {
                    succ = root;
                    root = root.left;
                } else {
                    break;
                }
            }
            return succ;
        }
        
        private TreeNode findMin(TreeNode root) {
            TreeNode min = root;
            while (root.left != null) {
                min = root.left;
                root = root.left;
            }
            return min;
        }
    

Log in to reply
 

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