Inorder Successor in Binary Search Tree

题目：

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

分析：

这道题目用dfs就比较慢，不用dfs逻辑很难，容易出错！

这道题用到BST性质可以强行简化整个步骤，我在做的时候第一个想到了dfs，结果忽视了BST这个事实。dfs也有一个好处，也就是普通Binary Tree也可以做，暂且记录在解法2里面。

解法1主要需要注意一下四点：

(1) 先做一个while循环，root ！= NULL 且 root->val != p->val。这样一来出循环的时候 要么找不到，要么找到。循环的过程中，如果向左孩子走，则parent = root，如果向右孩子走，则不记录parent，因为inorder的原理告诉我们 ！！！Parent并不是右孩子的successor！！！

(2) 接下来判断，如果root == NULL出来，说明没找到返回NULL即可

(3) 接下来，既然找到了，如果没有右孩子，肯定返回parent；这时候parent的值本身有两种可能，要么是NULL，要么是上一个结点，直接返回就可以

(4) *** 这里是最关键的一点，如果有右孩子，不能直接返回右孩子，需要找到右孩子最左边最深的结点，inorder的特性千万不要忽视！！！

解法2主要需要注意以下三点：

(1) 要保证只修改一次successor的值

(2) 要保证successor被修改过之后，剩余的递归直接return

(3) 注意，即使是pointer作为argument, 想修改它的值还是需要reference，所以有 TreeNode* &successor

解法1：

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // write your code here
        if (root == NULL || p == NULL) {
            return NULL;
        }

        TreeNode* parent = NULL;
        while (root != NULL && root->val != p->val) {
            if (root->val > p->val) {
                parent = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }

        if (root == NULL) {
            return NULL;
        } 

        if (root->right == NULL) {
            return parent;
        }

        root = root->right;
        while (root->left != NULL) {
            root = root->left;
        }
        return root;
    }
};

解法2：

class Solution {
public:
    void dfs(TreeNode* root, TreeNode* p, bool& isFound, TreeNode* &successor) {
        if (root == NULL) {
            return;
        }
        if (successor != NULL) {
            return;
        }
        dfs(root->left, p, isFound, successor);
        if (isFound && successor == NULL) {
            successor = root;
            return;
        }
        if (root->val == p->val) {
            isFound = true;
        }
        dfs(root->right, p, isFound, successor);
    }

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // write your code here
        if (root == NULL || p == NULL) {
            return NULL;
        }
        TreeNode* successor = NULL;
        bool isFound = false;
        dfs(root, p, isFound, successor);
        return successor;
    }
};