Fork me on GitHub

Inorder Successor in BST

Posted on

Description

https://leetcode.com/problems/inorder-successor-in-bst/

Solution

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
/**
 * 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) {
        if (root == NULL) return NULL;
        unordered_map<TreeNode*, int> mapping;
        vector<TreeNode*> vec;
        int index = 0;
        traverseNode(mapping, vec, root);
        int targetIndex = mapping[p];
        if (targetIndex >= vec.size() - 1) return NULL;
        return vec[targetIndex + 1];
    }
    
    void traverseNode(unordered_map<TreeNode*, int>& mapping, vector<TreeNode*>& vec, TreeNode* root) {
        if (root == NULL) return;
        traverseNode(mapping, vec, root->left);
        mapping[root] = vec.size();
        vec.push_back(root);
        traverseNode(mapping, vec, root->right);
        return;
    }
};

Quick Solution

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
/**
 * 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) {
        if (root == NULL) return NULL;
        TreeNode* traverse = root;
        TreeNode* ret = NULL;
        
        while (traverse) {
            if (p->val < traverse->val) {
                ret = traverse;
                traverse = traverse->left;
            }else {
                traverse = traverse->right;
            }
            
        }
        
        return ret;
    }
    
};