Simple Java recursive solution with in-order traversal


  • 2
    J

    The idea is returning the next node immediately after the target node (p) is hit.

    public class Solution {
      TreeNode target = null;
      public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    	if (root == null) 
    		return null;
    	TreeNode n = inorderSuccessor(root.left, p);
    	if (n != null)
    	    return n;
    	if (target == null) {
    	    if (root.val == p.val) 
    	    	target = root; 
    	} else {
    		return root;
    	}
    	return inorderSuccessor(root.right, p);
    } }

  • 0
    J

    Update: Added some optimization to the original code - skip the left subtree if p.val >= root.val during the traversal.

    public class Solution {
    TreeNode target = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    	if (root == null)
    		return null;
    	if (p.val < root.val) {
    		TreeNode n = inorderSuccessor(root.left, p);
    		if (n != null)
    			return n;
    	}
    	if (target == null) {
    		if (root.val == p.val)
    			target = root;
    	} else {
    		return root;
    	}
    	return inorderSuccessor(root.right, p);
    } }

Log in to reply
 

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