二叉樹的題目大多數時候就可以采用遞歸的方法寫
因為二叉樹是由根左子樹和右子樹組成，每一棵左子樹和右子樹又可以被看成一顆完整的樹，因此大事化小，小事化了

目的：就是判斷兩個樹是完全相同
思路：采用遞歸的方法，因為在二叉樹中樹是由根、左子樹和右子樹組成，每一個左子樹和右子樹又可以被看成一顆完整的樹，因此這里重要的是找好遞歸的截止條件就行

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//都為空的話就返回trueif(p==null&&q==null){return true;}//一個為空，一個不為空的話就返回falseif(p==null&&q!=null||p!=null&&q==null){return false;}//值不相同返回falseif(p.val!=q.val){return false;}//兩個不為空且值相同的話就繼續遞歸return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

class Solution {public boolean isSymmetric(TreeNode root) {//為空的話就返回trueif(root==null){return true;}//利用判斷是否相同的方法return isSymmetrichild(root.left,root.right);}public boolean isSymmetrichild(TreeNode left,TreeNode right){if(left==null&&right!=null||left!=null&&right==null){return false;}if(left==null&&right==null){return true;}if(left.val!=right.val){return false;}return isSymmetrichild(left.left,right.right)&&isSymmetrichild(left.right,right.left);}
}

目的：一棵樹左右深度差不大于1就是平衡二叉樹
這里從底到頂進行向上返回
思路：函數Height(root)來求其左子樹和右子樹深度差
返回值：
如果其深度差<=1：返回當前深度，
如果深度差>1就返回-1
中止條件：
root為空時候，說明找完了，返回當前高度為0
左子樹/右子樹深度為-1，或者深度差>1就返回-1，說明不是平衡二叉樹

class Solution {public boolean isBalanced(TreeNode root) {if(root==null){return true;}return Height(root)!=-1;      }//求樹的深度差public int Height(TreeNode root){if(root==null){return 0;}//求出左子樹和右子樹int left = Height(root.left);if(left<0){return -1;}int right = Height(root.right);if(right<0){return -1;}if(left>=0&&right>=0&&Math.abs(left-right)<=1){return left>right? left+1:right+1;}else{return -1;}}
}

如果這里不是平衡二叉樹，Height函數返回-1，如果是就返回其長度
所有子在isBalanced,只要判斷其返回是否是-1就行

目的：就是一棵二叉樹中的兩個節點p和q，找這兩個節點最近相同的公共祖先
思路：就是在root樹的左子樹和右子樹中找p和q,注意每一顆左子樹和右子樹又分別是一顆完整的樹
截止：找到節點或者root為null
返回值：如果left和right都不為null，那他們的祖先就是root節點
如果left != null ，返回left節點
如果right != null，返回right節點

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//1.判斷是否為空if(root==null){return null;}//2.是否找到p或者qif(root==q||root == p){return root;}//3.遞歸左子樹和右子樹進行判斷TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null){return root;}else if(left!=null){return left;}else{return right;}}
}

目的：就是給你一個前序遍歷字符串(由字母和‘#’構成)，’ # '表示的是空格，并中序打印
思路：1.先輸入一個字符串
2.創建這棵樹
3.中序遍歷打印
已知先序遍歷：根-》左子樹-》右子樹
中序遍歷：左子樹-》根-》右子樹

這里注意要先寫構造樹的類，這里創建樹采用遞歸
因為每一棵樹的左子樹和右子樹分別可以看成一顆完整的樹
這里再遞歸的時候，每個節點的左子樹和右子樹回遞歸，回歸的時候回將回歸這兩個節點鏈接起來

import java.util.Scanner;
//樹的構造方法類
class TreeNode{public char val;public TreeNode left;public TreeNode right;//構造方法給其val賦值public TreeNode(char val){this.val = val;}
}
// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的區別while (in.hasNextLine()) { // 注意 while 處理多個 case//1.輸入字符串String str = in.nextLine();//2.構建二叉樹TreeNode root = creatTree(str);//3.中序遍歷打印二叉樹inorder(root);}}//確定遍歷到那個字符public static int i = 0;public static TreeNode creatTree(String str){char ch = str.charAt(i);TreeNode root = null;if(ch!='#'){//將這個放入樹中root = new TreeNode(ch);i++;//指向下一個root.left = creatTree(str);root.right = creatTree(str);}else{i++;}return root;}//打印public static void inorder(TreeNode root){if(root == null){return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}
}