leetcode原题 后继者：找出二叉搜索树中指定节点的“下一个”节点

题目：

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例：

输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2

解题思路：

我们可以中序遍历二叉树，在找到p节点后，做一个标记，当遍历到它的后继时，发现标记为真，那么当前节点就是节点p的下一个节点，返回即可。

源代码如下：

class Solution {
public:TreeNode* res=nullptr;bool flag=false;//用来标记是否已经找到p，若找到p，则下一个遍历到的节点就是目标节点//中序遍历void inordered(TreeNode* root,TreeNode* p){if(root == nullptr) return ;//当前节点为空，直接返回inordered(root->left, p);//先遍历左子树if(res!=nullptr) return;//如果res不为空，说明已经找到目标节点//如果当前节点=p，则将flag更新if(root == p){flag=true;}//如果flag为真，则说明当前节点就是目标节点else if(flag){//将节点赋值给res，并返回res=root;return;}//继续遍历右子树inordered(root->right, p);}TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(root==nullptr) return nullptr;//对二叉树进行中序遍历，在遍历过程中找目标节点inordered(root, p);return res;}
};

 简化一下：

因为是中序遍历，那么p的下一个节点，一定是中序序列中，第一个比p节点大的节点，所以找到第一个比p大的节点即可。

源代码如下：

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