408算法题leetcode--第18天

98. 验证二叉搜索树

• 98. 验证二叉搜索树
• 思路：注释，前序遍历；也可以用中序遍历，当前节点值<上一个节点值
• 时间和空间：O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* root, long long lower, long long upper){
        if(root == nullptr) return true;
        if(root->val >= upper || root->val <= lower) return false;  // 开区间
        return check(root->left, lower, root->val) && check(root->right, root->val, upper); 
    }
    bool isValidBST(TreeNode* root) {
        // 1. 参数和返回类型：TreeNode*, longlong, longlong; bool
        // 2. 终止条件：节点为空, true
        // 3. 递归思路：前序遍历，先判断节点是否在合理范围中，然后递归左右子树
        return check(root, LONG_MIN, LONG_MAX);
    }
};

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

• 230. 二叉搜索树中第 K 小的元素
• 思路：中序遍历
• 时间和空间：O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ret;
    int count;

    void dfs(TreeNode* root){
        if(root == nullptr){
            return;
        }
        dfs(root->left);
        if(--count == 0){
            ret = root->val;
            return;
        }
        dfs(root->right);
    }

    int kthSmallest(TreeNode* root, int k) {
        // 可以用数组存放中序遍历的结果，然后返回v[k - 1]
        // 只记录第k小的数，用res记录
        count = k;
        dfs(root);
        return ret;
    }
};

704. 二分查找

• 704. 二分查找
• 时间：O(logn)；空间：O(1)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // lower_bound: 最小的i，使得nums[i] >= target
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < target){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if(nums[l] != target) return -1;
        return l;
    }
};

374. 猜数字大小

• 374. 猜数字大小
• 时间和空间：同二分

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(guess(mid) == 1){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};