剑指offer专项突击版第18天

剑指 Offer II 053. 二叉搜索树中的中序后继

方法一、直接中序遍历获得序列，然后查找p的下一个即可

class Solution {
    
public:
    void inorder(TreeNode *root, vector<TreeNode*> &ls){
    
        if(!root) return;
        inorder(root->left,ls);
        ls.emplace_back(root);
        inorder(root->right,ls);
    }
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    
        vector<TreeNode*> ls;
        inorder(root,ls);
        if(ls.back() == p) return nullptr;
        for(int i = 0; i < ls.size(); i++) {
    
            if(ls[i] == p) return ls[i+1];
        }
        return nullptr;
    }
};

方法二、利用二叉树的性质，左子树所有子节点小于当前结点，并且右子树所有子节点大于当前子节点。

class Solution {
    
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    
        TreeNode* res = nullptr;
        TreeNode *node = root;
        while(node != nullptr) {
    
            if(node->val > p->val) {
    
                res = node; //node的值会越来越接近p，这里res实时更新结点
                node = node->left;
            } else {
     //小于等于p结点就走right
                node = node->right;
            }
        }
        return res;
    }
};

---

剑指 Offer II 054. 所有大于等于节点的值之和

使用右中左的中序遍历即可，那么遍历获得的序列肯定就是降序的。接下来把前面累加的值加到当前结点即可。

class Solution {
        
public:
    void inorder(TreeNode* root, int &sum) {
    
        if(!root) return;
        inorder(root->right,sum);
        sum += root->val;
        root->val = sum;
        inorder(root->left,sum);
    }
    TreeNode* convertBST(TreeNode* root) {
    
        int sum = 0;
        inorder(root,sum);
        return root;
    }
};

---

剑指 Offer II 055. 二叉搜索树迭代器

求出中序遍历序列放入队列中，如果next操作就弹出队列即可。

class BSTIterator {
    
private:
    TreeNode *root;
    queue<TreeNode*> que;    
public:
    BSTIterator(TreeNode* root) {
    
        this->root = root;
        inorder(root);
    }
    
    int next() {
    
        int num = que.front()->val;
        que.pop();
        return num;
    }
    
    bool hasNext() {
    
        return que.size();
    }

    void inorder(TreeNode *root) {
    
        if(!root) return;
        inorder(root->left);
        que.push(root);
        inorder(root->right);
    }
};

利用栈模拟中序遍历过程

class BSTIterator {
    
private:
    TreeNode* cur;
    stack<TreeNode*> stk;
public:
    BSTIterator(TreeNode* root): cur(root) {
    }
    
    int next() {
    
        while (cur != nullptr) {
    
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        int ret = cur->val;
        cur = cur->right;
        return ret;
    }
    
    bool hasNext() {
    
        return cur != nullptr || !stk.empty();
    }
};