Leetcode 285. Inorder Successor in BST (Medium) (cpp)
Tag: Tree
Difficulty: Medium
/* 285. Inorder Successor in BST (Medium) Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note: If the given node has no in-order successor in the tree, return null. */ /** * 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) { stack<TreeNode*> s; iniSucSta(root, p, s); if (!s.empty() && s.top() == p) { getNextSuccessor(s); } return getNextSuccessor(s); } private: void iniSucSta(TreeNode* root, TreeNode* p, stack<TreeNode*>& s) { while (root != NULL) { if (root->val > p->val) { s.push(root); root = root->left; } else if (root->val < p->val) { root = root->right; } else { s.push(root); break; } } } TreeNode* getNextSuccessor(stack<TreeNode*>& s) { if (s.empty()) { return NULL; } TreeNode* cur = s.top(); s.pop(); TreeNode* temp = cur; cur = cur->right; while (cur != NULL) { s.push(cur); cur = cur->left; } return temp; } };
