1.

思路：

就是让左孩子和右孩子进行交换，这里需要一个中间变量用来记录，然后完成交换。如果进行优化则添加当左孩子和右孩子都为null时直接返回。

class Solution {public TreeNode invertTree(TreeNode root) {TreeNode tmp=null;//用来进行交换的中间变量if(root==null){return null;}if(root.left==null&&root.right==null){//如果是叶子结点return root;}//将该结点的左右孩子进行交换tmp=root.left;root.left=root.right;root.right=tmp;//交换完后，继续交换左孩子和右孩子的下一代invertTree(root.left);invertTree(root.right);return root;//返回根结点}
}

2.

思路：

判断两颗树是不是相同的树，一共有两个方面需要判断，一个是结构是否相同，一个是值是否相同，在结构上，我们判断两棵树相同位置是否存在相同的结点，一共有四种情况：

1.两个结点都为空

2.两个结点都不为空

3.A树的结点为空，B树的结点不为空

4.A树的结点不为空，B树的结点为空

其中3，4的情况都可以判断出这两棵树是不相同的，所以可以直接返回false

1可以判断相同，因为为空，所以值也不用进行判断，2的情况下，判断了结构是相同的，但还要继续判断值是否一样，如果值不一样，也返回false，如果值也一样，说明该位置的结点是一样的，接下来判断左右子树，如此类推

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//如果两个结点都为空if(p==null&&q==null){return true;}//如果两个结点都不为空if(p!=null&&q!=null){if(p.val==q.val){//如果两个结点值为一样return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);//继续判断左右子树是否一样}else{//如果两个结点值为不一样return false;}}//如果其中一个结点为空，另一个结点不为空return false;}
}

3.

思路：

判断根结点的左右子树是否对称，主要看两个方面，一个是结构，然后是值，这跟上面那道判断是否是相同树的题类似，只不过传参的时候，一个传左子树的左孩子和右子树的右孩子，一个传左子树的右孩子和右子树的左孩子

class Solution {public boolean isSameNode(TreeNode leftTree,TreeNode rightTree){//两个都为空if(leftTree==rightTree&&leftTree==null){return true;}//其中一个为空，另外一个不为空if(leftTree==null&&rightTree!=null||leftTree!=null&&rightTree==null){return false;}//两个都不为空但是值不一样if(leftTree.val!=rightTree.val){return false;}//两个都不为空且值一样return isSameNode(leftTree.left,rightTree.right)&&isSameNode(leftTree.right,rightTree.left);}public boolean isSymmetric(TreeNode root) {//如果是空树if(root==null){return true;}//判断左右子树是否对称return isSameNode(root.left,root.right);}
}

4.

思路：

平衡二叉树就是每一个结点的左右子树的高度都相差小于等于1，所以只需要遍历每个结点，然后求出每个结点左右子树的高度，进行判断高度是否相差小于等于1即可

class Solution {public boolean isBalanced(TreeNode root) {if(root==null){//如果结点为空return true;}int left=getHeight(root.left);//求左树高度int right=getHeight(root.right);//求右树高度if(Math.abs(left-right)>1){//如果不是平衡二叉树return false;}else{//继续遍历左右结点return isBalanced(root.left)&&isBalanced(root.right);}}public int getHeight(TreeNode node){if(node==null){//结点为空return 0;//高度为0}int left=getHeight(node.left);//左子树高度int right=getHeight(node.right);//右子树高度return (left>right?left:right)+1;//高的子树的高度加1}
}

但是这样子效率很低，首先要遍历所有结点，并且每个结点求高度又要遍历该结点的所有子结点，时间复杂度达到了O（n^2），因此虽然思路简单，但是效率不高。

字节面试就曾问过，在时间复杂度不超过O（n）的情况下，完成本题

原来求一个结点高度时，就已经从叶子结点开始往上递归求得高度，然后又遍历子结点，又要从叶子结点又往上递归求高度，有许多重复的计算，也是为什么第一种代码效率低下的原因

所以关键点就是要优化这里，如何求高度的同时就判断出是否是平衡二叉树？这时就可以发现，我们求高度的方法是求出左右子树的高度，然后高的子树的高度加1，那么此时我们已经得到了左右子树的高度，只需要判断一下高度相差是否超过1即可，这样子就可以在求高度的同时，判断出下面的结点是否是平衡二叉树

class Solution {public boolean isBalanced(TreeNode root) {if(root==null){return true;}int left=getHeight(root.left);int right=getHeight(root.right);//如果有-1，说明左右子树不是平衡二叉树，或者根结点的左右子树高度相差超过1if(left<0||right<0||Math.abs(left-right)>1){return false;}else{return true;}}public int getHeight(TreeNode node){if(node==null){return 0;}int left=getHeight(node.left);int right=getHeight(node.right);if(left<0||right<0||Math.abs(left-right)>1){//如果发现不是平衡二叉树return -1;//返回-1作为标记}else{return (left>right?left:right)+1;//正常求高度}}
}

 5.

思路：

前提知识：二叉搜索树有一个特性，就是左边子结点的值一定比父结点的值小，右边子结点的值一定比父结点的大，根据这个特性，如果使用中序遍历的话，那么就将是一个有序的从小到大的排列

根据题目描述，left作为前驱，right作为后继

当我们继续中序遍历时，最先到的是4

这时我们需要一个prev结点用来记录前一个结点的位置，此时prev初始化为null

4的left指向prev，prev记录为4，此时4的后继是6，但是现在拿不到6，所以先暂时如此

然后递归回退到6，6的left指向prev，prev记录为6，但是在这两步之间，应该让prev的right指向6，形成双向链表

但是在4时，prev还为null，所以这时候需要特殊判断一下

这样就将二叉树通过中序遍历，变成了一条有序的双向链表

这时候只需要定义一个结点head，循环当head.left != null，head=head.left，最后跳出循环就能找到4这个结点

返回head即可

public class Solution {public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree==null){//如果为空树return null;}Convertchild(pRootOfTree);//将二叉树变为双向链表TreeNode head=pRootOfTree;//定义一个头结点while(head.left!=null){//一直找到最左下角的结点head=head.left;}return head;//此时head就是中序遍历到的第一个结点}TreeNode prev=null;//用来记录前一个结点public void Convertchild(TreeNode root){//使二叉搜索树变为双向链表if(root==null){return;}Convertchild(root.left);//先左//进行转化root.left=prev;//left指向前一个结点if(prev!=null){//除了一开始时prev.right=root;//前面的结点的right指向当前结点        }prev=root;//记录当前结点为prevConvertchild(root.right);//后右}
}

6.

思路：

首先是有多组数据，所以要用hasnextLine（）来读取，然后用一个变量i来遍历字符串，同时定义一个返回值为树结点的方法叫creatTree，在这个方法里，定义一个树结点初始为null，如果i对应的字符不是#，则创建对应字符的结点，i往后走一位，然后让该结点的左孩子等于创建左树，让该结点的右孩子创建右树。如果等于#，则什么也不做，i往后走一位。最后的返回值都为创建的新结点

因为每次遍历中，i的值都保留原来的位置，所以i得是全局静态变量，又因为有可能有多组数据，所以每次处理完一组数据后，i要重新赋值为0，为下一组数据做准备

import java.util.Scanner;class TreeNode{//定义树的类public char val;public TreeNode left;public TreeNode right;TreeNode(char val){//构造方法this.val=val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);while(in.hasNextLine()){//多组数据String str=in.nextLine();TreeNode root=CreatTree(str);inorderTree(root);//中序打印i=0;//清零，为下一组数据作准备System.out.println();//打印完一组数据换行}}public static int i=0;public static TreeNode CreatTree(String str){TreeNode root=null;//如果是#就直接返回nullif(str.charAt(i)!='#'){root=new TreeNode(str.charAt(i));//创建结点i++;root.left=CreatTree(str);//创建左树root.right=CreatTree(str);//创建右树}else{i++;}return root;}public static void inorderTree(TreeNode root){if(root==null){return;}inorderTree(root.left);//先左System.out.print(root.val+" ");//打印inorderTree(root.right);//后右}
}