题目链接
LeetCode 面试题 04.06. 后继者[1]
题目描述
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回 null。
示例1
输入：root = [2,1,3], p = 1 2 / \1 3输出：2
示例2
输入：root = [5,3,6,2,4,null,null,1], p = 6 5 / \ 3 6 / \ 2 4 / 1输出：null
题解
BST+递归
首先本题中的二叉树还是个二叉搜索树，也就是中序遍历是单调递增的，所以我们可以利用这个性质来简化查找过程。
- 如果结点
p的值大于等于root的值，说明p的后继结点在root右子树中，那么就递归到右子树中查找。 - 如果结点
p的值小于root的值，说明p在root左子树中，而它的后继结点有两种可能，要么也在左子树中，要么就是root：
- 如果左子树中找到了后继结点，那就直接返回答案。
- 如果左子树中没有找到后继结点，那就说明
p的右儿子为空，那么root就是它的后继结点。
BST+非递归
- 如果
p有右儿子，那么它的后继结点就是右子树的最左边的儿子。 - 如果
p没有右儿子，那么它的后继结点就是，沿着p往上到root的路径中，第一个左儿子在路径上的结点。因为这个结点的左子树中p是最右边的结点，是最大的，所以它就是p的后继结点。因为是二叉搜索树，我们就可以从根结点开始往p走，根据结点值的大小决定走的方向。
一般树+递归
那如果是一般的二叉树，中序遍历就不满足单调递增了，这时候我们就只能找出中序遍历的结点顺序，然后才能得到 p 的后继结点。
所以我们直接采用递归来做中序遍历就行了，中序遍历结果保存下来，最后取 p 的下一个结点。
一般树+非递归
当然还可以采用栈来做中序遍历，这样就是非递归了。同样结果保存下来，最后取 p 的下一个结点。
一般树+Morris遍历
如果看过我前两天的一道关于二叉搜索树的题解：
【每日算法Day 73】学妹大半夜私聊我有空吗，然后竟然做出这种事！
韦阳的博客：【每日算法Day 73】学妹大半夜私聊我有空吗，然后竟然做出这种事！[2]
知乎专栏：【每日算法Day 73】学妹大半夜私聊我有空吗，然后竟然做出这种事！[3]
那么你一定会知道这个 Morris 遍历算法，用常数空间来解决结点无法访问父结点的问题。这里就不细讲了，请直接看之前的题解。方法是一样的，用 Morris 遍历得到中序遍历，然后遍历一遍找到 p ，输出它的下一个结点就行了。
代码
BST+递归（c++）
classSolution { public: TreeNode*inorderSuccessor(TreeNode*root, TreeNode*p) { if (root==NULL||p==NULL) returnNULL; if (p->val>=root->val) { returninorderSuccessor(root->right, p); } else { TreeNode*left=inorderSuccessor(root->left, p); returnleft?left : root; } } };
BST+非递归（c++）
classSolution { public: TreeNode*inorderSuccessor(TreeNode*root, TreeNode*p) { if (p->right) { p=p->right; while (p->left) p=p->left; returnp; } TreeNode*res=NULL; while (root!=p) { if (root->val<p->val) { root=root->right; } else { res=root; root=root->left; } } returnres; } };
一般树+递归（c++）
classSolution { public: voidinorder(TreeNode*root, vector<TreeNode*>&res) { if (root->left) inorder(root->left, res); res.push_back(root); if (root->right) inorder(root->right, res); } TreeNode*inorderSuccessor(TreeNode*root, TreeNode*p) { vector<TreeNode*>res; inorder(root, res); res.push_back(NULL); for (inti=0; i<res.size(); ++i) { if (res[i] ==p) { returnres[i+1]; } } returnNULL; } };
一般树+非递归（c++）
classSolution { public: TreeNode*inorderSuccessor(TreeNode*root, TreeNode*p) { vector<TreeNode*>res; TreeNode*rightmost=NULL; while (root) { if (root->left) { rightmost=root->left; while (rightmost->right&&rightmost->right!=root) { rightmost=rightmost->right; } if (rightmost->right!=root) { rightmost->right=root; root=root->left; } else { res.push_back(root); rightmost->right=NULL; root=root->right; } } else { res.push_back(root); root=root->right; } } res.push_back(NULL); for (inti=0; i<res.size(); ++i) { if (res[i] ==p) { returnres[i+1]; } } returnNULL; } };
参考资料
[1]
LeetCode 面试题 04.06. 后继者: https://leetcode-cn.com/problems/successor-lcci/
[2]
【每日算法Day 73】学妹大半夜私聊我有空吗，然后竟然做出这种事！: https://godweiyang.com/2020/03/18/leetcode-99/
[3]
【每日算法Day 73】学妹大半夜私聊我有空吗，然后竟然做出这种事！: https://zhuanlan.zhihu.com/p/114143194
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
