LeetCode Hot100 | Day4 | 层序遍历&&有序数组转搜索树&&验证搜索树&&搜索树中第K小的元素

102.二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

完整代码：

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root==nullptr)
            return res;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            vector<int> path;
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                q.pop();
                path.push_back(t->val);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            res.push_back(path);
        }
        return res;
    }
};

108.将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

层序遍历来做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode *tra(vector<int> nums)
    {
        if(nums.size()==0)
            return nullptr;
        int index=nums.size()/2;
        TreeNode *t=new TreeNode(nums[index]);
        t->left=tra(vector<int>(nums.begin(),nums.begin()+index));
        t->right=tra(vector<int>(nums.begin()+index+1,nums.end()));
        return t;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return tra(nums);
    }
};

98.验证二叉搜索树

记得要用二叉搜索树的性质，中序遍历有序

98. 验证二叉搜索树 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode *pre=nullptr;

    bool tra(TreeNode *t,int maxVal)
    {
        if(t==nullptr)
            return true;
        bool l=tra(t->left,maxVal);
        if(pre!=nullptr)
            if(t->val<=pre->val)
                return false;
        pre=t;
        bool r=tra(t->right,maxVal);
        return l&&r;
    }
    bool isValidBST(TreeNode* root) {
        int maxVal=INT_MIN;
        return tra(root,maxVal);
    }
};

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

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

1.转为有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> nums;
    void tra(TreeNode *t)
    {
        if(t==nullptr)
            return;
        tra(t->left);
        nums.push_back(t->val);
        tra(t->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        tra(root);
        return *(nums.begin()+k-1);
    }   
};

2.中序遍历

每走过一个数，计数器count++，k==count的时候那就是结果了，res记录结果然后返回

后面的情况都不会发生res的覆盖了，因为count只会比k大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int res=0;
    int count=0;
    void tra(TreeNode *t,int k)
    {
        if(t==nullptr)
            return;
        tra(t->left,k);
        count++;
        if(k==count)
        {
            res=t->val;
            return;
        }
        tra(t->right,k);
    }
    int kthSmallest(TreeNode* root, int k) {
        tra(root,k);
        return res;
    }   
};

K神题解，一开始用的k–，但是发现会覆盖，就改成加了，没想到加个==0就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        this->k = k;
        dfs(root);
        return res;
    }
private:
    int res, k;
    void dfs(TreeNode* root) {
        if (root == nullptr) return;
        dfs(root->left);
        if (k == 0) return;
        if (--k == 0) res = root->val;
        dfs(root->right);
    }