Massive Algorithms: LeetCode 285- Inorder Successor in Binary Search Tree

LeetCode 285- Inorder Successor in Binary Search Tree

http://buttercola.blogspot.com/2015/10/leetcode-inorder-successor-in-bst.html

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

Note: If the given node has no in-order successor in the tree, return null.

Brute-force solution: O(n)
The most straight-forward solution is to do a in-order traversal of the BST. When we found the target node, we look for the smallest number greater than the node.

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {

        if (root == null || p == null) {

            return null;

}

        if (p.right != null) {

            return findMin(p.right);

}

        // Case 2: p.right == null

        TreeNode succ = null;

        TreeNode q = root;

        while (q != null) {

            if (q.val > p.val) {

                succ = q;

                q = q.left;

            } else if (q.val < p.val) {

                q = q.right;

            } else {

                break;

}

}

        return succ;

}

    private TreeNode findMin(TreeNode root) {

        TreeNode p = root;

        while (p.left != null) {

            p = p.left;

}

        return p;

}

X. https://blog.csdn.net/qq508618087/article/details/50886124
思路: 一种较为通用的方法是中序遍历一遍二叉树,记录结点的前一个结点,这样当前一个结点为p时,当前结点就是p的后继结点.这种方法适用于一般二叉树,时间复杂度为O(n).

但是这种方法并没有利用到二叉搜索树的性质. 因此我们还可以比较给定结点与根结点的大小, 如果根节点的值较大, 说明这个结点在根节点的左边, 因此此时根节点就是其不紧切后继, 然后再往左子树去比较. 如果根节点值较小, 说明我们要找的结点在根节点右边.这样一步步就可以找到最终的后继.
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if(!root) return root;
inorderSuccessor(root->left, p);
if(pre == p) ans = root;
pre = root;
inorderSuccessor(root->right, p);
return ans;
}
private:
TreeNode *pre = NULL, *ans = NULL;
http://www.cnblogs.com/grandyang/p/5306162.html

这种方法充分地利用到了BST的性质，我们首先看根节点值和p节点值的大小，如果根节点值大，说明p节点肯定在左子树中，那么此时我们先将res赋为root，然后root移到其左子节点，循环的条件是root存在，我们再比较此时root值和p节点值的大小，如果还是root值大，我们重复上面的操作，如果p节点值，那么我们将root移到其右子节点，这样当root为空时，res指向的就是p的后继节点，参见代码如下：

cr    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *res = NULL;
        while (root) {
            if (root->val > p->val) {
                res = root;
                root = root->left;
            } else root = root->right;
        }
        return res;
    }

上面那种方法也可以写成递归形式，写法也比较简洁，但是需要把思路理清，当根节点值小于等于p节点值，说明p的后继节点一定在右子树中，所以对右子节点递归调用此函数，如果根节点值大于p节点值，那么有可能根节点就是p的后继节点，或者左子树中的某个节点是p的后继节点，所以先对左子节点递归调用此函数，如果返回空，说明根节点是后继节点，返回即可，如果不为空，则将那个节点返回，参见代码如下：

解法四:

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root) return NULL;
        if (root->val <= p->val) {
            return inorderSuccessor(root->right, p);
        } else {
            TreeNode *left = inorderSuccessor(root->left, p);
            return left ? left : root;
        }
    }

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if(!root || !p) return NULL;
TreeNode* ans = NULL;
while(root)
{
if(root->val > p->val)
{
ans = root;
root = root->left;
}
else root = root->right;
}
return ans;
}
Inorder Successor in Binary Search Tree - GeeksforGeeks
Method 1 (Uses Parent Pointer)
In this method, we assume that every node has parent pointer.
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.
Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.
1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it's parent. The parent of such a node is the succ.
Also http://algorithms.tutorialhorizon.com/inorder-successor-in-binary-search-tree-using-parent-link/

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

  // step 1 of the above algorithm 

  if( n->right != NULL )

    return minValue(n->right);

  // step 2 of the above algorithm

  struct node *p = n->parent;

  while(p != NULL && n == p->right)

{

     n = p;

     p = p->parent;

}

  return p;

}

/* Given a non-empty binary search tree, return the minimum data  

    value found in that tree. Note that the entire tree does not need

    to be searched. */

struct node * minValue(struct node* node) {

  struct node* current = node;

  /* loop down to find the leftmost leaf */

  while (current->left != NULL) {

    current = current->left;

}

  return current;

}

Method 2 - No parent node
1) If right subtree of node is not NULL, then succ lies in right subtree:
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then start from root and use search like below:
Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise go to left side.
Also check http://algorithms.tutorialhorizon.com/inorder-successor-in-binary-search-tree-without-using-parent-link/
http://www.cnblogs.com/jcliBlogger/p/4829200.html
http://blog.csdn.net/fightforyourdream/article/details/19860143

struct node * inOrderSuccessor(struct node *root, stuct node *n)

{

    // step 1 of the above algorithm

    if( n->right != NULL )

        return minValue(n->right);

    struct node *succ = NULL;

    // Start from root and search for successor down the tree

    while (root != NULL)

{

        if (n->data < root->data)

{

            succ = root;

            root = root->left;

}

        else if (n->data > root->data)

            root = root->right;

        else

           break;

}

    return succ;

}

Why?
LeetCode [285] Inorder Successor in BST

Note: If the given node has no in-order successor in the tree, return null.

The most straight-forward solution is to do a in-order traversal of the BST. When we found the target node, we look for the smallest number greater than the node.

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {

        if (root == null || p == null) {

            return null;

}

        if (p == root) {

            return p.right;

}

        Stack<TreeNode> stack = new Stack<>();

        TreeNode q = root;

        while (!stack.isEmpty() || q != null) {

            if (q != null) {

                stack.push(q);

                q = q.left;

            } else {

                TreeNode curr = stack.pop();

                q = curr.right;

                if (curr == p) {

                    if (curr.right != null) {

                        TreeNode m = curr.right;

                        while (m.left != null) {

                            m = m.left;

}

                        return m;

                    } else if (!stack.isEmpty()){

                        return stack.pop();

}

}

}

}

        return null;

}

http://www.meetqun.com/thread-10973-1-1.html

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null || p == null) {
return null;9 E+ U$ W7 U/ @* ?$ o: X& v3 R7 U
}2 P" B( M) X, _' O; W @
if (root.left == null && root.right == null) {
return null;! j1 P; x/ Q' U/ T
}4 C9 y' s. t+ }/ p4 v: O
List<TreeNode> list = new LinkedList<TreeNode>();
helper(root, p.val, list);
if (list.size() == 0) {) Q# o) z4 [; U% }8 ^$ g
return null;
}
return list.get(0);
}% l9 U7 H# v! W* q5 ^
) ^) i% O* |# g' [) q
private void helper(TreeNode root, int targetValue, List<TreeNode> list) {
if (root == null) {
return;& G5 t- Q. V7 k) v
}7 J2 K2 F! m; X6 F
helper(root.left, targetValue, list);% y& @% ]7 r6 c- b
if (root.val > targetValue && list.size() == 0) {( p/ x1 G6 D2 [0 x
list.add(root);/ I, x2 P* ~* }( O
}
helper(root.right, targetValue, list);8 g: i4 X c2 x7 b9 G+ m, b( h
}9

http://www.cnblogs.com/yrbbest/p/5037889.html
http://www.cnblogs.com/jcliBlogger/p/4829200.html
我们先建立一个空的successor，再取得一个root节点的reference。每次当node.val > p.val的时候，我们记录下当前的node节点，然后往左子树查找。否则向右子树查找。向右子树查找的过程中不需要更新successor。

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

http://www.jiuzhang.com/solutions/inorder-successor-in-bst/

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null && root.val != p.val) {
            if (root.val > p.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        
        if (root == null) {
            return null;
        }
        
        if (root.right == null) {
            return successor;
        }
        
        root = root.right;
        while (root.left != null) {
            root = root.left;
        }
        
        return root;
    }

http://buttercola.blogspot.com/2015/10/leetcode-inorder-successor-in-bst.html

If a node n doesn't have a right subtree, then we are done traversing n's subtree. We need to pick up where we left off with n's parent, which we'll call q.

If n was to the left of q, then the next node we should traverse should be q (again, since left - > current -> right).

If n were to the right of q, then we have fully traversed q's subtree as well. We need to traverse upwards from q until we find a node x that we have not fully traversed. How do we know that we have not fully traversed a node x? We know we have hit this case when we move from a left node to its parent. The left node is fully traversed, but its parent is not.

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {

        if (root == null || p == null) {

            return null;

}

        if (p.right != null) {

            return findMin(p.right);

}

        // Case 2: p.right == null

        TreeNode succ = null;

        TreeNode q = root;

        while (q != null) {

            if (q.val > p.val) {

                succ = q;

                q = q.left;

            } else if (q.val < p.val) {

                q = q.right;

            } else {

                break;

}

}

        return succ;

}

    private TreeNode findMin(TreeNode root) {

        TreeNode p = root;

        while (p.left != null) {

            p = p.left;

}

        return p;

}

http://leetcode.tgic.me/inorder-successor-in-bst/index.html

12     TreeNode leftMost(TreeNode root){
13         if(root == null) return null;
14         if(root.left != null) return leftMost(root.left);
15         return root;
16     }
17 
18     public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
19         if(root == p) {
20             return leftMost(p.right);
21         }
22 
23         if(p.val < root.val) {
24             p = inorderSuccessor(root.left, p);
25 
26             if(p == null){
27                 return root;
28             }
29 
30             return p;
31         }
32 
33         return inorderSuccessor(root.right, p);
34     }

TreeNode inorderSucc(TreeNode n) {
if (n == null) return null;

/* Found right children -> return leftmost node of right subtree. */
if (n.right != null) {
return leftMostChild(n.right);
} else {
TreeNode q = n;
TreeNode x = q.parent;
// Go up until we're on left instead of right
while (x != null && x.left != q) {
q = x;
x = x.parent;
}
return x;
}
}

TreeNode leftMostChild(TreeNode n) {
if (n == null) {
return null;
}
while (n.left != null) {
n = n.left;
}
return n;
}
Read full article from Inorder Successor in Binary Search Tree - GeeksforGeeks

LeetCode 285- Inorder Successor in Binary Search Tree

Labels

Popular Posts