-
Notifications
You must be signed in to change notification settings - Fork 28
/
Copy pathInorder_Successor_in_BST.cpp
37 lines (37 loc) · 1.01 KB
/
Inorder_Successor_in_BST.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* curr = root;
while(curr) {
if(!curr->left) {
TreeNode* parent = curr;
curr = curr->right;
if(parent == p) {
while(curr and curr->left) {
curr = curr->left;
}
return curr;
}
} else {
TreeNode* leftNode = curr->left;
TreeNode* rightMost = leftNode;
while(rightMost->right) {
rightMost = rightMost->right;
}
rightMost->right = curr;
curr->left = nullptr;
curr = leftNode;
}
}
return root;
}
};