leetcode6.12-6.25
6.12
二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
private:int res=0,cnt=0;
public:
int kthSmallest(TreeNode* root, int k) {
inorder(root,k);
return res;
}
void inorder(TreeNode* root,int k){
if(root==nullptr) return;
inorder(root->left,k);
cnt++;
if(cnt==k){
res=root->val;
return;
}
inorder(root->right,k);
}
};
|
中序遍历二叉搜索树可以使结果有序，注意res,cnt要设为全局变量，不要作为递归函数的参数进入递归的过程。
6.13
按照二叉树的通用思路，需要思考每个节点应该做什么，但是这道题上很难想到什么思路。
BST 的每个节点左小右大，这似乎是一个有用的信息，既然累加和是计算大于等于当前值的所有元素之和，那么每个节点都去计算右子树的和，不就行了吗？
这是不行的。对于一个节点来说，确实右子树都是比它大的元素，但问题是它的父节点也可能是比它大的元素呀？这个没法确定的，我们又没有触达父节点的指针，所以二叉树的通用思路在这里用不了。
其实，正确的解法很简单，还是利用 BST 的中序遍历特性。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
private: int sum=0;
public:
TreeNode* convertBST(TreeNode* root) {
if(root==nullptr) return root;
convertBST(root->right);
sum+=root->val;
root->val=sum;
convertBST(root->left);
return root;
}
};
|
把递归顺序改成先右后左，就可以降序
6.14
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
private: long long inorder = (long long)INT_MIN - 1;
public:
bool isValidBST(TreeNode* root) {
if(root==nullptr){
return true;
}
if(!isValidBST(root->left)){
return false;
}
if(root->val<=inorder)
return false;
inorder=root->val;
if(!isValidBST(root->right))
return false;
return true;
}
};
|
中序遍历，如果它的中序遍历是升序的，那么它就是一棵二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root==nullptr){
return nullptr;
}
if(root->val>val){
return searchBST(root->left,val);
}
if(root->val<val){
return searchBST(root->right,val);
}
return root;
}
};
|
这里的话不要用遍历的想法，用分解问题的思维模式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr){
return new TreeNode(val);
}
if(root->val<val){
root->right=insertIntoBST(root->right,val);
}
if(root->val>val){
root->left=insertIntoBST(root->left,val);
}
return root;
}
};
|
6.21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int numTrees(int n) {
vector<vector<int>> res(n+1,vector<int>(n+1,0));
return count(1,n,res);
}
int count(int l,int r,vector<vector<int>>& res){
if(l>r){
return 1;
}
if(res[l][r]!=0){
return res[l][r];
}
int result=0;
for(int i=l;i<=r;i++){
int left=count(l,i-1,res);
int right=count(i+1,r,res);
result+=left*right;
}
res[l][r]=result;
return result;
}
};
|
用分解问题的思维模式，
如果固定某一个点为根节点，那么有几种树的情况，
根据二叉搜索树的特性，那么根节点的左子树都比根节点小，节点是1-n的有序数组，那么就是根节点左边的数，
右子树的话就是根节点右边的数，那么计算出根节点左子树能够组成多少种树，计算出右子树能够组成多少种树，以该根节点就有：左子树可能数量*右子树可能数量 种情况。那么分别计算出1-n每个数为根节点时树的可能数量，累加即可。为了消除重叠子问题，需要加一个备忘录。
6.23
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
28
| class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
return build(1,n);
}
vector<TreeNode*> build(int l,int r){
vector<TreeNode*> res;
if(l>r){
res.push_back(nullptr);
return res;
}
for(int i=l;i<=r;i++){
vector<TreeNode*> left=build(l,i-1);
vector<TreeNode*> right=build(i+1,r);
for(auto j:left){
for(auto k:right){
TreeNode* root=new TreeNode(i);
root->left=j;
root->right=k;
res.push_back(root);
}
}
}
return res;
}
};
|
与前一题不同的地方在于需要在遍历寻找所有可能的二叉搜索树的时候构造每一棵树。
最难的地方就在于怎么去构造，这个方法以分解问题的思维模式，针对一个根节点，得到所有这个节点所有可能的左（右）子树的根节点的集合，然后对每一种情况都分别进行构造，因此new root的操作要放在循环里面。
关键在于每一层的返回值和最底部的处理条件。
6.24
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root==nullptr){
return true;
}
int left=findheight(root->left);
int right=findheight(root->right);
if(!judgeheight (left,right)){
return false;
}
bool left1=isBalanced(root->left);
bool right1=isBalanced(root->right);
return left1&right1;
}
int findheight(TreeNode* root) {
if(root==nullptr){
return 0;
}
int left=findheight(root->left);
int right=findheight(root->right);
return max(left,right)+1;
}
bool judgeheight(int left,int right){
if(left<right){
if(right-left>1){
return false;
}
else return true;
}
else {
if(left-right>1){
return false;
}
else return true;
}
}
};
|
6.25
这道题主要涉及到了回溯，在遍历找到叶子节点之后需要回溯到根节点
需要一个结果向量来保存每一次遍历到叶子节点得到的路径，以及一个用来存放每次遍历经过的节点的向量。
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
28
29
30
31
32
| class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> result;
if(root==nullptr) return result;
travel(root,path,result);
return result;
}
void travel(TreeNode* root, vector<int>& path, vector<string>& result){
path.push_back(root->val);
if(root->left==nullptr&&root->right==nullptr){
string spath;
for(int i=0;i<path.size()-1;i++){
spath+=to_string(path[i]);
spath+="->";
}
spath+=to_string(path[path.size()-1]);
result.push_back(spath);
return;
}
if(root->left){
travel(root->left,path,result);
path.pop_back();
}
if(root->right){
travel(root->right,path,result);
path.pop_back();
}
return;
}
};
|
- 当当前节点不为空，且该节点的左右节点都为空时，找到叶子节点
- 找到叶子节点后需要把path向量里面的节点拼接成结果字符串并放入result中
- 回溯和递归是一一对应的，有一个递归，就要有一个回溯
这道题有点陷入用分解问题的方式解决问题的思维误区了，其实只要遍历这个树的过程中找到左叶子就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
private: int sum =0;
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr){
return 0;
}
if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr){
sum+=root->left->val;
}
sumOfLeftLeaves(root->left);
sumOfLeftLeaves(root->right);
return sum;
}
};
|