leetcode6.4-6.11
最近是二叉树专题
6.4
数的问题有两种思维模式，一种是遍历的思维模式，另一种是分解问题的思维模式。拿到题目后根据题目选择思维模式。
这道题首先想到的是保存前序遍历的结果然后对保存的结果（即每个节点）做处理。但是也用了额外的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void flatten(TreeNode* root) {
if(root==nullptr){
return;
}
vector<TreeNode*> res;
firsttravel(root,res);
for(int i=0;i<res.size()-1;i++){
res[i]->left=nullptr;
res[i]->right=res[i+1];
}
}
void firsttravel(TreeNode* root,vector<TreeNode*>& r){
if(root==nullptr){
return;
}
r.push_back(root);
firsttravel(root->left,r);
firsttravel(root->right,r);
}
};
|
看了题解后得到了一种比较好的解法—-用分解问题的思维模式
定义：输入节点 root，然后 root 为根的二叉树就会被拉平为一条链表
1
| void flatten(TreeNode* root);
|
对于一个节点 x，可以执行以下流程：
1、先利用 flatten(x.left) 和 flatten(x.right) 将 x 的左右子树拉平。
2、将 x 的右子树接到左子树下方，然后将整个左子树作为右子树。
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
|
void flatten(TreeNode* root) {
if (root == nullptr) return;
flatten(root->left);
flatten(root->right);
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
root->right = left;
TreeNode* p = root;
while (p->right != nullptr) {
p = p->right;
}
p->right = right;
}
|
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
6.5
用分解问题的思维模式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size()==0) return nullptr;
int index=-1,max=INT_MIN;
for(int i=0;i<nums.size();i++){
if(nums[i]>max){
max=nums[i];
index=i;
}
}
TreeNode* root = new TreeNode(max);
vector<int> left1(nums.begin(), nums.begin() + index);
root->left=constructMaximumBinaryTree(left1);
vector<int> right1(nums.begin()+index+1, nums.end());
root->right=constructMaximumBinaryTree(right1);
return root;
}
};
|
要注意max要设置为最小整数，因为设置成0的话，有数组中用例=0时，index=-1没有被覆盖，left1构造的时候会报错
6.6
一看到题，绝对经典，基本都碰到过这样的一道数据结构题。现在让你写出算法解决
看了题解后才会做
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:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder,0,preorder.size()-1,
inorder,0,inorder.size()-1);
}
TreeNode* build(vector<int>& preorder,int prestart,int preend,
vector<int>& inorder,int instart,int inend)
{
if (prestart > preend || instart > inend)
return nullptr;
int rootval=preorder[prestart];
int index=0;
for(int i=instart;i<=inend;i++){
if(inorder[i]==rootval){
index=i;
break;
}
}
TreeNode* root=new TreeNode(rootval);
root->left=build(preorder,prestart+1,prestart+index-instart,
inorder,instart,index-1);
root->right=build(preorder,prestart+index-instart+1,preend,
inorder,index+1,inend);
return root;
}
};
|
一开始的时候没有加这样的一个判断条件
1
2
| if (prestart > preend || instart > inend)
return nullptr;
|
导致了报了数组越界的错误，后面一想如果没有这个判断不仅会导致递归过程中数组的越界，也没有设置递归的终止条件，这个判断必须得有。
这道题也是用分解问题的思维模式去做
根节点是前序遍历数组的第一个
关键点在于通过根节点的值，得到左子树前序和中序的新数组，右子数前序和中序的新数组
- 得到根节点的值之后就可以在中序数组中确认左子树的数组和该数组的大小
- 通过这个大小可以在前序中确认左子树的数组
6.7
同昨天的题一个系列，这次是中序和后序，后面还有前序和后序
思路和前一题一样，中序和后序确认新数组的方式有所区别
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:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return bulid(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
}
TreeNode* bulid(vector<int>& inorder,int instart,int inend,
vector<int>& postorder,int poststart,int postend)
{
if(instart>inend||poststart>postend){
return nullptr;
}
int rootval=postorder[postend];
int index=0;
for(int i=instart;i<=inend;i++){
if(inorder[i]==rootval){
index=i;
break;
}
}
TreeNode* root=new TreeNode(rootval);
root->left=bulid(inorder,instart,index-1,
postorder,poststart,poststart+index-instart-1);
root->right=bulid(inorder,index+1,inend,
postorder,poststart+index-instart,postend-1);
return root;
}
};
|
首先要注意的是前序和后序不能确定唯一的二叉树，所以返回任意一种可能的答案。
于前面两题有所区别的是，在通过前序得到根节点后，怎么判断该节点属于左子树的全部节点是数组的那一部分即无法确切的知道左右子树有哪些节点。
1、首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。
2、然后把前序遍历结果的第二个元素作为左子树的根节点的值。
3、在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。
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
| class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
return build(preorder,0,preorder.size()-1,postorder,0,postorder.size()-1);
}
TreeNode* build(vector<int>& preorder,int prestart,int preend,
vector<int>& postorder,int poststart,int postend)
{
if(prestart>preend||poststart>postend){
return nullptr;
}
if(prestart==preend){
return new TreeNode(preorder[prestart]);
}
int rootval=preorder[prestart];
TreeNode* root =new TreeNode(rootval);
int index=0;
int lefti=preorder[prestart+1];
for(int i=poststart;i<=postend;i++){
if(postorder[i]==lefti){
index=i;
break;
}
}
root->left=build(preorder,prestart+1,prestart+index-poststart+1,
postorder,poststart,index);
root->right=build(preorder,prestart+index-poststart+2,preend,
postorder,index+1,postend-1);
return root;
}
};
|
6.8
说实话这题题目都没怎么看懂，根本没有思路，上题解
1.如何知道以这个节点为根的二叉树长什么样
需要在后序位置写代码，因为得先知道该节点的左右子树长什么样，然后就是将遍历结果序列化，可以用前序顺序或者后序顺序拼接字符串，但是不能用中序顺序
2.以其他节点为根的子树长什么样
借助unordered_map把每个节点的序列化结果保存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
private:
unordered_map<string,int> map;
vector<TreeNode*> ans;
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
serialize(root);
return ans;
}
string serialize(TreeNode* root){
if(root==nullptr){
return "#";
}
string left=serialize(root->left);
string right=serialize(root->right);
string res=to_string(root->val)+","+left+","+right;
map[res]++;
if(map[res]==2) ans.push_back(root);
return res;
}
};
|
6.9
297. 二叉树的序列化与反序列化 - 力扣（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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Codec {
public:
string serialize(TreeNode* root) {
string res;
serialize(root,res);
return res;
}
void serialize(TreeNode*& root,string& s){
if(root==NULL){
s+="null,";
return;
}
s+=to_string(root->val)+",";
serialize(root->left,s);
serialize(root->right,s);
return;
}
TreeNode* deserialize(string data) {
list<string> dataArray;
string str;
for(auto& ch :data) {
if(ch==','){
dataArray.push_back(str);
str.clear();
}
else {
str.push_back(ch);
}
}
if(!str.empty()){
dataArray.push_back(str);
str.clear();
}
return rdeserialize(dataArray);
}
TreeNode* rdeserialize(list<string>& dataArray){
if(dataArray.front()=="null"){
dataArray.erase(dataArray.begin());
return NULL;
}
TreeNode* root =new TreeNode(stoi(dataArray.front()));
dataArray.erase(dataArray.begin());
root->left=rdeserialize(dataArray);
root->right=rdeserialize(dataArray);
return root;
}
};
|
用的是前序，有一点要注意
如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。
如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，分两种情况：
2.1. 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。
2.2. 如果你给出前序和后序，那么除非你的整棵树中不包含值相同的节点，否则你无法还原出唯一的一棵二叉树。
如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
3.1. 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。
3.2. 如果你给出的是中序，那么除非你的整棵树中不包含值相同的节点，否则你无法还原出唯一的一棵二叉树。
6.10
6.11
这两天忙租房的事情，断了两天。。