Massive Algorithms: LeetCode - Inorder Successor in BST II

http://www.cnblogs.com/grandyang/p/10424982.html

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

The successor of a node p is the node with the smallest key greater than p.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.

Example 1:

Input: 
root = {"$id":"1","left":{"$id":"2","left":null,"parent":{"$ref":"1"},"right":null,"val":1},"parent":null,"right":{"$id":"3","left":null,"parent":{"$ref":"1"},"right":null,"val":3},"val":2}
p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of Node type.

Example 2:

Input: 
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":1},"parent":{"$ref":"2"},"right":null,"val":2},"parent":{"$ref":"1"},"right":{"$id":"5","left":null,"parent":{"$ref":"2"},"right":null,"val":4},"val":3},"parent":null,"right":{"$id":"6","left":null,"parent":{"$ref":"1"},"right":null,"val":6},"val":5}
p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null

这道题是之前的那道 Inorder Successor in BST 的后续，之前那道题给了我们树的根结点，而这道题并没有确定给我们根结点，只是给了树的任意一个结点，然后让求给定结点的中序后继结点。这道题比较好的一点就是例子给的比较详尽，基本覆盖到了大部分的情况，包括一些很tricky的情况。首先来看例子1，结点1的中序后继结点是2，因为中序遍历的顺序是左-根-右。还是例子1，结点2的中序后续结点是3，这样我们就知道中序后续结点可以是其父结点或者右子结点。再看例子2，结点6的中序后续结点是空，因为其已经是中序遍历的最后一个结点了，所以没有后续结点。例子3比较tricky，结点15的中序后续结点不是其右子结点，而是其右子结点的左子结点17，这样才符合左-根-右的顺序。例子4同样tricky，结点13的中序后继结点并不是其亲生父结点，而是其祖爷爷结点15。

好，看完了这四个例子，我们应该心里有些数了吧。后继结点出现的位置大致可以分为两类，一类是在子孙结点中，另一类是在祖先结点中。仔细观察例子不难发现，当某个结点存在右子结点时，其中序后继结点就在子孙结点中，反之则在祖先结点中。这样我们就可以分别来处理，当右子结点存在时，我们需要找到右子结点的最左子结点，这个不难，就用个while循环就行了。当右子结点不存在，我们就要找到第一个比其值大的祖先结点，也是用个while循环去找即可，参见代码如下：

    Node* inorderSuccessor(Node* node) {
        if (!node) return NULL;
        Node *res = NULL;
        if (node->right) {
            res = node->right;
            while (res && res->left) res = res->left;
        } else {
            res = node->parent;
            while (res && res->val < node->val) res = res->parent;
        }
        return res;
    }
}

public Node inorderSuccessor(Node x) {
  Node result = null;
 
  //case 1: right child is not null -> go down to get the next
  Node p = x.right;
  while(p!=null){ 
    result = p;
    p = p.left;
  }
 
  if(result != null){
    return result; 
  }
 
  //case 2: right child is null -> go up to the parent, 
  //until the node is a left child, return the parent
  p = x;
 
  while(p!=null){
    if(p.parent!=null && p.parent.left==p){
      return p.parent;
    } 
    p = p.parent;
  }
 
  return null;
}

LeetCode - Inorder Successor in BST II

Labels

Popular Posts