[LeetCode]Inorder Successor in BST

找后继结点，递归的思路，如果当前节点的值小于等于给定节点，去右子树找。否则，当前节点curr有可能是答案，那么我们需要去左子树找，如果能找到，我们return在左子树找到的值，因为其值比curr小，否则我们return curr的值。时间复杂度O(log n)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
	if(!root)return nullptr;
	if(root->val > p->val)
	{
	auto findLeft = inorderSuccessor(root->left, p);
	return findLeft? findLeft: root;
	}
	else if(root->val <= p->val)
	return inorderSuccessor(root->right, p);
	}
	};

view raw Inorder Successor in BST.cpp hosted with ❤ by GitHub