LeetCode 面试题 04.06 后继者[二叉搜索树 递归] HERODING的LeetCode之路

解题思路：
第一个方法是递归，如果当前节点值小，不断往右找，大了之后，再往左找，如果返回null就是当前节点，否则返回左找的节点，代码如下:

class Solution {    
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(root == nullptr) return nullptr;
        // 如果当前根的值小于等于p的值，向右找
        if(root->val <= p->val) {
            return inorderSuccessor(root->right, p);
        }
        // 否则是当前节点或者左子树上
        TreeNode* node = inorderSuccessor(root->left, p);
        return node == nullptr ? root : node;
    }
};

循环遍历的方式也很简单的，相同的思路，首先定义ans为nullptr，这样如果target是最大值，就直接返回nullptr了，然后不断遍历到刚好比target大的节点，再往它左子树遍历，左子树没有，返回该节点，否则返回该节点的最左子节点，代码如下：

class Solution {    
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* cur = root;
        TreeNode* ans = nullptr;
        while(cur != nullptr) {
            if(cur->val <= p->val) {
                cur = cur->right;
            } else {
                ans = cur;
                cur = cur->left;
            }
        }
        return ans;
    }
};