【leetcode】【剑指offer Ⅱ】053. 二叉搜索树中的中序后继
问题描述：
- 给定一棵二叉搜索树和其中的一个节点
p，找到该节点在树中的中序后继。如果节点没有中序后继，请返回null。- 节点
p的后继是值比p.val大的节点中键值最小的节点，即按中序遍历的顺序节点p的下一个节点。
- 节点
核心思路：
- 该题有两种解题方法。
- 方法一：中序遍历二叉搜索树，用两个变量记录当前节点与前一个节点。
- 如果上一个访问的节点是节点
p，则当前访问节点是p的中序后继。
- 如果上一个访问的节点是节点
- 方法二：利用二叉搜索树的性质。
- 如果
root -> val <= p -> val，则结果必定在root的右子树中。 - 否则结果必定在
root的左子树中或这就是root。
- 如果
代码实现：
- 方法一代码实现如下：
class Solution { private: TreeNode* cur = nullptr; TreeNode* next = nullptr; void dfs(TreeNode* root, TreeNode* p) { if(!root) return; dfs(root->left, p); if(cur) { next = next ? next : root; return; } if(root == p) cur = p; dfs(root->right, p); return; } public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { dfs(root, p); return next; } }; - 方法二代码实现如下：【下述代码为递归版本，代码贴自评论区】
class Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { if (!root) return root; if (root -> val <= p -> val) return inorderSuccessor(root -> right, p); auto left = inorderSuccessor(root -> left, p); return !left ? root : left; } };