出处：剑指offer07
题目：输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
思路：前序遍历：中左右，中序遍历：左中右。前序遍历的第一个结点就是根结点，通过根结点对中序遍历进行划分得到左子树和右子树，分别递归对其他结点也进行这样的递归得到划分后的二叉树。
注意点：对于前、中、后序遍历的划分如下所示：
TreeNode* build(int pre_start,int pre_end,int in_start,int in_end)
{
//前序：中左右 中序：左中右
if(pre_start>pre_end)
return NULL;
if(in_start>in_end)
return NULL;
int val=_preorder[pre_start];
TreeNode *node=new TreeNode(val);
int k=hash[val];
int left_size=k-in_start;
node->left=build(pre_start+1,pre_start+1+left_size,in_start,k-1);
node->right=build(pre_start+1+left_size,pre_end,k+1,in_end);
return node;
}?已知中序和后序重建二叉树：
//node* create(int postL, int postR, int inL,int inR)
//{
// if (postL > postR)
// return NULL;
// node* root = new node;
// root->data = postorder[postR];//后序遍历的最后一个结点是根节点
// int k;//记录根中序遍历节点位置
// for (k = 0; k <= inR; k++)
// {
// if (postorder[postR] == inorder[k])
// {
// break;
// }
// }
// int num_left = k - inL;//左结点个数
// root->lchild = create(postL, postL + num_left - 1, inL, k - 1);
// root->rchild = create(postL + num_left, postR - 1, k + 1, inR);
// return root;
//}出处：剑指offer026
题目：
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
思路：
递归三步求解
1.返回值：返回是否是子结构
2.终止条件：如果递归时A（大树）为空返回false,B（子结构）空返回true。
3.单步递归逻辑：当A,B结点中的值相同时，同时判断func(A->left,B)||func(A->right,B) B是否存在与A的左子树或右子树中。
bool isSubStructure(TreeNode* A, TreeNode* B)
{
if(!A||!B)return false;
if(A->val==B->val&&check(A->left,B->left)&&check(A->right,B->right))
{
return true;
}
return isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
bool check(TreeNode* A, TreeNode* B)
{
if(!B)
return true;
if(!A)
return false;
if(A->val==B->val)
return check(A->left,B->left)&&check(A->right,B->right);
else
return false;
}出处：剑指offer27
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
?思路：后序遍历，递归
1.返回：输出镜像树的根节点
2.终止条件：当结点为null时返回null
3.单步逻辑：后序遍历拿到中结点的左右子结点，交换两个结点。
TreeNode* mirrorTree(TreeNode* root)
{
if(!root)
return NULL;
mirrorTree(root->left);
mirrorTree(root->right);
TreeNode *left=root->left;
TreeNode *right=root->right;
root->left=right;
root->right=left;
return root;
}出处： 剑指offer28
题目：判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
思路：二叉树对称要求左子树的左结点等于右子树的右结点，并且左子树的右节点等于右子树的左结点
递归
1.返回值：返回bool
2.终止条件：如果root1&&root2则返回true，如果root1或root2有一个为null或当前结点值不相同返回false
3.单步逻辑：返回func(A->left,B->right)&&func(A->right,B->left)
bool check(TreeNode* root1, TreeNode* root2)
{
//终止条件
if (root1 == NULL && root2 == NULL)return true;
else if (root1 == NULL && root2 != NULL)return false;
else if (root1 != NULL && root2 == NULL)return false;
//单层递归
if (root1->val != root2->val)return false;
bool flag1=check(root1->left, root2->right);
bool flag2=check(root1->right, root2->left);
bool isSame = flag1 && flag2;
return isSame;
}
bool isSymmetric(TreeNode* root)
{
if (root==NULL)
return true;
else return check(root->left,root->right);
}