Mind palace

some thoughts

0%

285. Inorder Successor in BST

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

O(h) time O(h) space
递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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) return root;
        if (root->val <= p->val) return inorderSuccessor(root->right, p);
        auto l = inorderSuccessor(root->left, p);
        return l ? l : root;
    }
};

循环版 O(h) time O(1) space
比p大的第一个节点要不是p的父节点（p是其父节点的左子）要不在p的右子树上，从root开始往下找，如果当前的root比p大，说明这个点有可能是p的父节点，即有可能是最终解，先存下来继续往下找，如果当前的root不比p大，说明这个点肯定不是最终解，最终解要不已经被存下来（之前的最近的父节点）要不就还在右子树上，则继续沿着右子树往下找，如果在右子树上找到了符合要求的（比p大的）节点，则存下来更新res，直到找到叶节点为止，复杂度就是树高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 *res = nullptr;
        while (root) {
            if (root->val <= p->val) {
                root = root->right;
            } else {
                res = root;
                root = root->left;
            }
        }
        return res;
    }
};

binary tree版本
O(n) time O(h) space

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) {
        dfs(root, p->val);
        return res;
    }

    void dfs(TreeNode *root, int v) {
        if (!root) return;
        dfs(root->left, v);
        if (res) return; // 找到就立即返回
        if (pre && pre->val == v) {
            res = root;
			return; // 找到就立即返回
        }
        pre = root;
        dfs(root->right, v);
    }

    TreeNode *pre = nullptr, *res = nullptr;
};
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
/**
 * 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) return root;
        auto l = inorderSuccessor(root->left, p);
        if (found_p && !found_res) {
            found_res = true;
            return root;
        }
        if (found_p && found_res) return l;
        if (root->val == p->val) {
            found_p = true;
        }
        return inorderSuccessor(root->right, p);
    }

    bool found_p = false, found_res = false;
};