二叉树中等题

98. 验证二叉搜索树

本题要求验证二叉搜索树是否有效，也就是递归比较验证左子树的节点都严格小于当前节点，右子树的节点都严格大于右子树。

class Solution {
public:
    bool check(TreeNode* root,long long lower,long long upper){
        if(root==nullptr) return true;

        if(root->val<=lower || root->val >=upper) return false;
        return check(root->left,lower,root->val) && check(root->right,root->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        return check(root,LLONG_MIN,LLONG_MAX);
    }
};

230. 二叉搜索树中第 K 小的元素

本题要找第 k 小的元素，结合前面前面中序遍历得到的列表直接是一个升序列表，所以最简单的思路直接是中序遍历然后取 k-1 下标即可

class Solution {
public:
    void inorder(TreeNode* root,vector<int>& res){
        if(!root) return;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        inorder(root,res);
        return res[k-1];
    }
};

在上面的方法中我们存储了整个遍历出来的列表，但是实际上只用得到一个，所以我们可以在不需要的时候直接忽略掉，只存储需要的第 k 个元素。

class Solution {
public:
    int value=0;
    int i=0;
    void inorder(TreeNode* root,int k){
        if(!root) return;
        inorder(root->left,k);
        i++;
        if(i==k){
            value=root->val;
        }
        inorder(root->right,k);
    }
    int kthSmallest(TreeNode* root, int k) {
        inorder(root,k);
        return value;
    }
};

用迭代写法可以适当优化空间

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* curr=root;
        while(!st.empty() || curr!=nullptr){
            while(curr!=nullptr){
                st.push(curr);
                curr=curr->left;
            }
            curr=st.top();
            st.pop();
            k--;
            if(k==0){
                return curr->val;
            }
            curr=curr->right;
        }
        return -1;
    }
};

199. 二叉树的右视图

题目让去二叉树从右侧看到的节点值的数组……完全不说任何，翻译一下：每层最右节点组成的升序列表。

走层序遍历把每层最后一个 pop 出的值加进列表即可。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();
                if(i==size-1){
                    res.push_back(node->val);
                }
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
        }
        return res;
    }
};