LeetCode 面试题 04.06. 后继者

思路

中序遍历，储存结果，顺序查找，找到目标下标。时间复杂度(O(2n))，空间复杂度(O(n))。

代码

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
/**
 * 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:
    void InOrder(TreeNode* root,vector<TreeNode*> &res){
        if(root->left!=nullptr) InOrder(root->left,res);
        res.push_back(root);
        if(root->right!=nullptr) InOrder(root->right,res);
    }
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        vector<TreeNode*> res;
        InOrder(root,res);
        int k=-1;
        for(int i=0;i<res.size();i++){
            if(res[i]==p){
                k=i+1;
                break;
            }
        }
        return k==-1||k>=res.size()?nullptr:res[k];
    }
};

参考

  1. https://leetcode.cn/problems/successor-lcci/ ↩