重构二叉树
输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树：
特别感谢：[bilibili正月点灯笼大佬]
（https://www.bilibili.com/video/av7420546?from=search&seid=3738404029614420188）
思路：题目中给了我们先序遍历和中序遍历；在二叉树的前序遍历中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树位于根结点的左边，而右子树位于根结点的右边。因此我们可以根据前序遍历找到根结点，根据中序遍历确定左右子树。
代码实现：
public TreeNode rebuildBinaryTree(int preorder[], int inorder[]) {
if (preorder == null || inorder == null) { //如果前序或者中序有一个是空直接返回，确定特殊值空值！！！
return null;
}
// 定义构建二叉树的核心算法
TreeNode root = rebuildBinaryTreeCore(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);
return root;
}
// 构建二叉树的核心算法 前序遍历序列{1,2,4,7,3,5,6,8}
// 中序遍历序列{4,7,2,1,5,3,8,6}
public TreeNode rebuildBinaryTreeCore(int preorder[], int startPreorder,int endPreorder,
int inorder[], int startInorder, int endInorder) {
if (startPreorder > endPreorder || startInorder > endInorder) { //停止递归的条件
return null;
}
TreeNode root = new TreeNode(preorder[startPreorder]);
for (int i = startInorder; i <= endInorder; i++) {
if (preorder[startPreorder] == inorder[i]) {
// 其中（i - startInorder）为中序排序中左子树结点的个数
//左子树
root.left = rebuildBinaryTreeCore(preorder, startPreorder + 1,
startPreorder + (i - startInorder), inorder,startInorder, i - 1);
//右子树
root.right = rebuildBinaryTreeCore(preorder, (i - startInorder)+ startPreorder + 1,
endPreorder, inorder, i + 1,endInorder);
}
}
return root;
}
举一反三，已知二叉树的中序和后序遍历重构二叉树
另一个树的子树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
代码：
public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
boolean result = false;
//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
if (root2 != null && root1 != null) {
//如果找到了对应Tree2的根节点的点
if(root1.val == root2.val){
//以这个根节点为为起点判断是否包含Tree2
result = doesTree1HaveTree2(root1,root2);
}
//如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
if (!result) {
result = HasSubtree(root1.left,root2);
}
//如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
if (!result) {
result = HasSubtree(root1.right,root2);
}
}
//返回结果
return result;
}
public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
//如果Tree2已经遍历完了都能对应的上，返回true
if (node2 == null) {
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if (node1 == null) {
return false;
}
//如果其中有一个点没有对应上，返回false
if (node1.val != node2.val) {
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
}
