描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：n≤2000，节点的值 −10000≤val≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
思路：利用递归
class Solution {
public:
TreeNode* reConstructBinaryTree(vector pre,vector vin) {
if(pre.empty()||vin.empty())
return NULL;
TreeNode* root=new TreeNode(pre[0]);
int tmp=0;
while(vin[tmp]!=pre[0]) tmp++;
root->left=reConstructBinaryTree(vector({pre.begin()+1,pre.begin()+1+tmp}),vector({vin.begin(),vin.begin()+tmp}));
root->right=reConstructBinaryTree(vector({pre.begin()+1+tmp,pre.end()}),vector({vin.begin()+tmp+1,vin.end()}));
return root;
}
};
重点：
- 如何截取vector中的一段，并作为参数或者返回值
vector({pre.begin()+1,pre.begin()+1+tmp})如何初始化treeNode，有点生疏了。
描述
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
思路：如果返回真有三种可能性：全部相等，左子树包含，右子树包含。而全部相等要检验每一个结点值。
class Solution {
public:
bool isSame(TreeNode* p1, TreeNode* p2){
if(!p2) return true;
else if(!p1) return false;
return p1->val==p2->val&&isSame(p1->left, p2->left)&&isSame(p1->right, p2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(!pRoot1||!pRoot2) return false;
return isSame(pRoot1,pRoot2)||HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
}
};
重点：
- 起初第一个想法是利用前序遍历，再类似字符串kmp一样检测是否有相同序列。后来发现树因为有左右子树的原因，导致排序不同，所以不能这样想。通常对称性递归的返回值是多个条件的复合判断语句（参考其他同学想法）
可能是以下几种条件判断的组合：
节点非空的判断
节点值比较判断
(单树)调用根节点左右子树的递归函数进行递归判断
(双树)调用两棵树的左右子树的递归函数进行判断
描述
操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 0≤n≤10000， 二叉树每个节点的值 0≤val≤10000
要求： 空间复杂度 O(n)。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n)
比如：
源二叉树
镜像二叉树
思路：DFS递归，每遇到一个结点就交换它的左右子树。
TreeNode* Mirror(TreeNode* pRoot) {
if(pRoot){
TreeNode* tmp=NULL;
tmp=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=tmp;
pRoot->left=Mirror(pRoot->left);
pRoot->right=Mirror(pRoot->right);
}
return pRoot;
}
重点：第一次写的时候忘了考虑根结点的NULL可能性
