Inorder Successor in Binary Search Tree

Inorder 1.png

Inorder 2.png

解題思路 ：

先解決 root == nullptr 的問題 直接回傳 root
之後判斷兩種狀況

1. p 點有 right child:
   這種情形 inorder 的下一個 successor 必須是 right child 子樹的最小值 ( 最左下層 )

2. p 點沒有 right child:
   此時要檢查是否有 parent 並且此 parent 的值要比 p 大 ( 這樣 p 才會是 parent 的 left child ) 在 inorder 中如果 p 為 left child 那 parent 就會是下一個出列

C++ code :

<pre><code>
TreeNode* findMin(TreeNode* p)
{

while(p->left != nullptr)

{
    p = p->left; 
}
return p;

}

class Solution {

public:

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    // write your code here
    if(root == nullptr) return root;
    //target has a right child
    if(p->right != nullptr) return findMin(p->right);
 
    //target has no right child
    TreeNode *parent = nullptr;
    TreeNode *tmp = root;
    while(tmp != p)
    {
        if(p->val < tmp->val)
        {
            parent = tmp;
            tmp = tmp->left;
        }
        else tmp = tmp->right;
    }
    return parent;
}

};