设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
示例：
输入: root = [2,1,3], p = 1
2
/
1 3
输出: 2
思路：
方法一： 二叉搜索树中序遍历
常规二叉树中序遍历搜索，由于只需要找到节点p的后继节点，我们只需要维护上一个节点和当前节点
时间复杂度O(n)
空间复杂度O(n)，取决于树的深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution1{
public:
TreeNode* inorderSuccessor(TreeNode *root, TreeNode* p){
stack<TreeNode*> st;
TreeNode *pre = nullptr, *cur = root;
while(!st.empty() || cur != nullptr){
while(cur != nullptr){
st.emplace(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
if(pre == p){
return cur;
}
pre = cur;
cur = cur->right;
}
return nullptr;
}
};
|
方法二：利用二叉搜索树的特性
具体可看二叉搜索树
二叉搜索树中序遍历是升序，所以找到当前节点的下一个节点就直接返回
时间复杂度为O(n),空间复杂度为O(1)
1
2
3
4
5
6
7
8
9
10
| 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);
}
};
|