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

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

102.二叉树的层序遍历

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

完整代码：

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）

层序遍历来做

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）

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.转为有序数组

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大

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就行了

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);}