LeetCode刷题实战285：二叉搜索树中的顺序后继
共 2322字，需浏览 5分钟
·
2021-06-08 02:16
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
The successor of a node p is the node with the smallest key greater than p.val.
示例
输入: root = [2,1,3], p = 1
输出: 2
解析: 这里 1 的顺序后继是 2。
请注意 p 和返回值都应是 TreeNode 类型。
解题
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
stack<TreeNode*> s;
bool b = false;
TreeNode *t = root;
while (t || !s.empty()) {
while (t) {
s.push(t);
t = t->left;
}
t = s.top(); s.pop();
if (b) return t;
if (t == p) b = true;
t = t->right;
}
return NULL;
}
};