226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]示例 2：
输入：root = [2,1,3]
输出：[2,3,1]示例 3：
输入：root = []
输出：[]提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return null;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}TreeNode类定义了二叉树的节点结构，每个节点包含三个属性：
val：节点的值。left：指向左子节点的引用。right：指向右子节点的引用。
Solution类中的invertTree方法接受一个TreeNode类型的参数root，表示二叉树的根节点。invertTree方法的逻辑如下：
- 如果当前节点
root为null，直接返回null，表示空树不需要翻转。 - 定义一个临时变量
tmp，用来交换左右子节点的引用。 - 将当前节点的左子节点引用赋值给
tmp。 - 将当前节点的右子节点引用赋值给左子节点，完成左右子节点的交换。
- 将
tmp（原左子节点）赋值给右子节点，完成左右子节点的交换。 - 递归调用
invertTree方法翻转左子树，即invertTree(root.left);。 - 递归调用
invertTree方法翻转右子树，即invertTree(root.right);。 - 返回翻转后的根节点
root。
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return cmp(root.left, root.right);
}
public boolean cmp(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return cmp(left.left, right.right) && cmp(left.right, right.left);
}
}TreeNode类定义了二叉树的节点结构，每个节点包含三个属性：
val：节点的值。left：指向左子节点的引用。right：指向右子节点的引用。
Solution类中的isSymmetric方法是用来判断给定的二叉树是否是对称的。对称的二叉树是指一个树的左子树和右子树是镜像对称的。isSymmetric方法的逻辑如下：
- 如果根节点
root为null，则返回true，因为空树是对称的。 - 调用
cmp方法比较根节点的左子树和右子树是否对称。
cmp方法是一个辅助方法，用于递归地比较两个节点left和right是否对称。其逻辑如下：
- 如果
left和right都为null，则它们是对称的，返回true。 - 如果
left和right中有一个为null而另一个不是，则它们不是对称的，返回false。 - 如果
left和right的值不相等，则它们不是对称的，返回false。 - 递归地比较
left的左子树和right的右子树是否对称，以及left的右子树和right的左子树是否对称。如果两者都是对称的，则返回true；否则返回false。
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 定义当前节点，是在某节点的左边还是右边
private Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
public TreeNode dealTree(int[] preorder, int[] inorder, int preLeft,int preRight, int inLeft,int inRight){
if (preLeft > preRight || inLeft > inRight){
return null;
}
// 当前节点的下标就是先序的第一个，也就是左边界preLeft
int nowPreIndex = preLeft;
// 那么当前节点，在中序遍历的下标是哪里呢？通过映射关系去找
int nowInIndex = indexMap.get(preorder[nowPreIndex]);
//计算一下，在本节点的左边的数据到底有多少，右边又有多少
int numLeft = nowInIndex - inLeft; // 通过当前下标减左边界下标得到
// 好，两边的下标都找到了，就不管了，开始处理本节点的事情
TreeNode now = new TreeNode(preorder[nowPreIndex]);
// 然后为他创建左右字数的内容
// 边界改变，前序左边界去掉了本节点，前序右边界也无需递归那么多（看到底再本节点的左边有多少），然后是前序左边界，到当前下标-1
now.left = dealTree(preorder,inorder,preLeft + 1 ,preLeft + numLeft,inLeft,nowInIndex-1);
now.right = dealTree(preorder,inorder,preLeft + numLeft +1 ,preRight,nowInIndex+1,inRight);
return now;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 通过中序遍历，创建对应的映射下标关系（可以快速分辨出对应的节点，是在当前节点的左边还是右边）
int num = inorder.length;
for (int i = 0 ;i< num ;i++) {
indexMap.put(inorder[i],i);
}
return dealTree(preorder, inorder, 0, num-1, 0,num-1);
}
}106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
/**
1、后序数组为0，空节点
2、后序数组中的最后一个元素为头节点
3、寻找中序数组位置进行切割
4、切中序数组(使用的是下标)
5、切后序数组(使用左区间大小和右区间大小)
6、递归处理左区间右区间。
root是根节点，递归遍历root左子树，递归遍历root右子树。
*/
/**
* java.lang.System 类
* public static native void arraycopy(Object src, int srcPos,
* Object dest, int destPos,
* int length);
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 如果后序数组为空，则返回null
if (postorder.length == 0) {
return null;
}
// 如果后序数组长度为1，直接返回对应的节点
if (postorder.length == 1) {
return new TreeNode(postorder[0]);
}
// 创建根节点
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
// 在中序数组中找到根节点的位置
int index = 0;
for (; index < inorder.length; index++) {
if (inorder[index] == root.val) {
break;
}
}
// 切割中序数组
int[] leftInOrder = new int[index];
System.arraycopy(inorder, 0, leftInOrder, 0, index);
int[] rightInOrder = new int[inorder.length - index - 1];
System.arraycopy(inorder, index + 1, rightInOrder, 0, inorder.length - index - 1);
// 切割后序数组
int[] leftPostOrder = new int[leftInOrder.length];
System.arraycopy(postorder, 0, leftPostOrder, 0, leftInOrder.length);
int[] rightPostOrder = new int[rightInOrder.length];
System.arraycopy(postorder, leftInOrder.length, rightPostOrder, 0, rightInOrder.length);
// 递归构建左子树和右子树
root.left = buildTree(leftInOrder, leftPostOrder);
root.right = buildTree(rightInOrder, rightPostOrder);
return root;
}
}
