14. 二叉树展开为链表
思路：递归，将子树展开为链表。根节点右节点为左节点，左节点的右节点为右节点，左节点设为空。
错误代码：
class Solution {
public:
void flatten(TreeNode* root) {
if(!root)
return;
if(root->left)
{
TreeNode* t1=root->left;
TreeNode* t2=root->right;
if(root->right)
{
root->right=t1;
t1->right=t2;
root->left=nullptr;
}
else
{
root->right=root->left;
root->left=nullptr;
}
}
flatten(root->left);
flatten(root->right);
}
};
错误原因：
递归不会写，思路不清晰。
正确代码：
class Solution {
public:
void flatten(TreeNode* root) {
if(!root)
return;
//将根节点的左子树变成链表
flatten(root->left);
//将根节点的右子树变成链表
flatten(root->right);
TreeNode* t=root->right;
//把树的右边换成左边的链表
root->right=root->left;
//把树的左边置空
root->left=nullptr;
//把右边链表接到最右边
while(root->right)
root=root->right;
root->right=t;
}
};
递归表达式要放到哪里呀
101. 对称二叉树
思路是：如果镜像对称，那么遍历中-左-右和中-右-左得到的结果应该一样。
难点是如何递归？
错误代码：
class Solution {
public:
bool compare(TreeNode* root1,TreeNode* root2)
{
if(root1->val==root2->val)
return true;
else
return false;
return compare(root1->left,root2->right);
return compare(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
TreeNode* root0=root;
if(!root)
return true;
return compare(root0,root);
}
};
错误原因：
正确代码：
方法一：递归法
class Solution {
public:
bool compare(TreeNode* root1,TreeNode* root2)
{
if(!root1&&!root2)
return true;
if(!root1||!root2)
return false;
return (root1->val==root2->val)&&compare(root1->left,root2->right)&&compare(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
return compare(root,root);
}
};
方法二：迭代法
初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
queue<TreeNode*> s;
s.push(root);
s.push(root);
while(!s.empty())
{
TreeNode* p=s.front();s.pop();
TreeNode* q=s.front();s.pop();
if(!p&&!q)
continue;
if((!p&&q)||(p&&!q)||(p->val!=q->val))
return false;
s.push(p->right);
s.push(q->left);
s.push(p->left);
s.push(q->right);
}
return true;
}
};
21 . 合并两个有序链表
错误代码：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1)
return l2;
if(!l2)
return l1;
while(l1->val>=l2->val)
{
ListNode* t=l2->next;
l2->next=mergeTwoLists(l1,t);
}
while(l1->val<l2->val)
{
ListNode* t=l1->next;
l1->next=mergeTwoLists(t,l2);
}
return l1;
}
};
错误原因：不知道最后返回什么？？
正确代码：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1)
return l2;
if(!l2)
return l1;
//自顶向下
//头结点为l2
if(l1->val>=l2->val)
{
//l2在前，比较l1和l2->next
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}
//头结点为l1
else
{
//l1在前，比较l1->next和l2
l1->next=mergeTwoLists(l1->next,l2);
return l1;
}
}
};
105. 从前序与中序遍历序列构造二叉树
完全没思路！根据根节点和左节点的位置顺序？如何构造？从下到上？
思路：
1、首先前序定位根节点；
2、在中序遍历找出对应根节点，并分辨出左右子树；
3、求左右子树长度，在前序遍历中找出子树；
4、递归。
逐个在前序找。然后中序找出索引。把那个索引的值的左边数组看为左子树，右边数组为右子树。
class Solution {
public:
int indexit(vector<int>& vec,int p)
{
vector<int>::iterator it=find(vec.begin(),vec.end(),p);
int dis=distance(vec.begin(),it);
return dis;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty())
return nullptr;
TreeNode *newTree= new TreeNode(preorder[0]);//初始化根节点
int loc=indexit(inorder,preorder[0]);//查找根节点在中序遍历中的位置
int l1=loc,l2=preorder.size()-loc-1;//左子树、右子树的长度
vector<int>leftTree(inorder.begin(),inorder.begin()+l1);//左子树结点中序
vector<int>rightTree(inorder.end()-l2,inorder.end());//右子树结点中序
vector<int>preleftTree(preorder.begin()+1,preorder.begin()+l1+1);//左子树前序
vector<int>prerightTree(preorder.end()-l2,preorder.end());//右子树前序
newTree->left=buildTree(preleftTree, leftTree);//递归子树
newTree->right=buildTree(prerightTree, rightTree);
return newTree;
}
};
