Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/285.html

 285	Inorder Successor in BST

 Given a binary search tree (See Definition) and a node in it,
 find the in-order successor of that node in the BST.

 Example

 Given tree = [2,1] and node = 1:
     2
    /
   1
 return node 2.

 Given tree = [2,1,3] and node = 2:
   2
  / \
 1   3
 return node 3.

 Note:
     If the given node has no in-order successor in the tree, return null.
     It's guaranteed that the values of the tree are unique.

 Challenge
     O(h), where h is the height of the BST.

 @tag-tree

Algorithm

If the value of the root node is less than or equal to the value of the p node, it means that the successor node of p must be in the right subtree, so this function is recursively called on the right child node.

If the value of the root node is greater than the value of p, then it is possible that the root node is the successor of p, or a node in the left subtree is a successor of p, * So first call this function recursively on the left child node, * If it returns empty, indicating that the root node is a successor node, just return, * If it is not empty, return that node

Code

  • 
    public class Inorder_Successor_in_BST {
    
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
        class Solution {
    
            public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    
                if (root == null) {
                    return null;
                }
    
                if (root.val <= p.val) {
                    return inorderSuccessor(root.right, p);
                }
                else {
                    TreeNode left = inorderSuccessor(root.left, p); //如果不是null,那么root就不是next
                    return left == null ? root : left;
                }
    
            }
        }
    
    }
    
    ############
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            TreeNode cur = root, ans = null;
            while (cur != null) {
                if (cur.val <= p.val) {
                    cur = cur.right;
                } else {
                    ans = cur;
                    cur = cur.left;
                }
            }
            return ans;
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/inorder-successor-in-bst/
    // Time: O(N)
    // Space: O(logN)
    class Solution {
    private:
        TreeNode *target, *ans = NULL;
        bool seen = false;
        void inorder(TreeNode *root) {
            if (!root) return;
            inorder(root->left);
            if (seen && !ans) ans = root;
            if (seen && ans) return;
            if (root == target) seen = true;
            inorder(root->right);
        }
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            target = p;
            inorder(root);
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    
    class Solution:
        def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
            cur, ans = root, None
            while cur:
                if cur.val <= p.val:
                    cur = cur.right
                else:
                    ans = cur
                    cur = cur.left
            return ans
    
    ############
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def inorderSuccessor(self, root, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        if root and q:
          flag = False
          stack = [(1, root)]
          while stack:
            p = stack.pop()
            if not p[1]:
              continue
            if p[0] == 0:
              if flag:
                return p[1]
              if p[1] == q:
                flag = True
            else:
              stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)])
    
          return None
    
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func inorderSuccessor(root *TreeNode, p *TreeNode) (ans *TreeNode) {
    	cur := root
    	for cur != nil {
    		if cur.Val <= p.Val {
    			cur = cur.Right
    		} else {
    			ans = cur
    			cur = cur.Left
    		}
    	}
    	return
    }
    
    
  • /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {TreeNode} p
     * @return {TreeNode}
     */
    var inorderSuccessor = function (root, p) {
        let cur = root;
        let ans = null;
        while (cur != null) {
            if (cur.val <= p.val) {
                cur = cur.right;
            } else {
                ans = cur;
                cur = cur.left;
            }
        }
        return ans;
    };
    
    

All Problems

All Solutions