第一題二叉樹的前序遍歷

給你二叉樹的根節點 root ，回傳它節點值的 前序 遍歷，

輸入：root = [1,null,2,3]
輸出：[1,2,3]

遞回就完事了，前序中序后序都一樣遍歷就行了，

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List <Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
        List<Integer>lefttree =preorderTraversal(root.left);
       list.addAll(lefttree);
         List<Integer>righttree =preorderTraversal(root.right);
         list.addAll(righttree);        
return list;
    }
}

有人就要問了為啥這個代碼不能直接
list.add(root.val);
preorderTraversal(root.right);
preorderTraversal(root.right);
這里要和大家解釋一下我們所用的list是一個區域變數，關鍵就是理解名字都是 list，但不是同一個變數，而是每次方法執行，都有一個 list，遞回回傳時需要一個list來接收，為什么是addAll因為你遞回不可能只遞回一次，

第二題檢查兩顆樹是否相同

給你兩棵二叉樹的根節點 p 和 q ，撰寫一個函式來檢驗這兩棵樹是否相同，

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，

輸入：p = [1,2,3], q = [1,2,3] 輸出：true

分析我們要先判斷如果都為空，或者一個為空另一個不為空的情況，然后如果相同了，我們就要看樹的左右結點是否相同，按這個思想遞回這來，

class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!=null&&q==null||p==null&&q!=null){
           return false;
       }
         if(p==null && q==null){
        return true;
       }
       if(p.val!=q.val){
          return  false;
       }
       return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
      
    }
}

第三題另一顆樹的子樹

給你兩棵二叉樹 root 和 subRoot ，檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹，如果存在，回傳 true ；否則，回傳 false ，
二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點，tree 也可以看做它自身的一棵子樹，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subtree-of-another-tree

輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
輸出：true
思路和上道題一樣，就是這道題我們需要遞回一下，如果這個結點的結構和該結構不一樣，我們就去遍歷該結構的左右結構，

class Solution {
    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root==null&&subRoot!=null||root!=null&&subRoot==null){
            return false;
    }
    if(root==null&&subRoot==null){
        return true;
    }
    if(root.val != subRoot.val){
        return false;
    }
    return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
           if(isSubtree(root.left,subRoot))return true;
           if (isSubtree(root.right,subRoot))return true;
            return false;
        }
}

第四題二叉樹最大深度

給定一個二叉樹，找出其最大深度，

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，

說明: 葉子節點是指沒有子節點的節點，

   3
 /  \
9  20
/   \
15   7
回傳它的最大深度 3 ，

思路
拿一個頭節點如果為空就沒有深度，如果有就為1，然后看子節點如果為空就深度為1，如果不為空就+1.

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
         int right=maxDepth(root.right);
        int  left=maxDepth(root.left);
        return left>right?left+1:right+1;
    }
}

第五題判斷一顆二叉樹是否是平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹，

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 ，

輸入：root = [3,9,20,null,null,15,7]
輸出：true
題解：這道題我們把他分解了之后會很容易，我們先判斷樹是不是空的然后判斷這個樹是不是平衡的（可以用四題的公式然后求出差值為一的樹結點），然后判斷子樹左右是不是也是平衡的，

class Solution {
     public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int right=maxDepth(root.right);
        int  left=maxDepth(root.left);
        return left>right?left+1:right+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftH= maxDepth(root.left);
       int rightH=maxDepth(root.right);
       return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);       
    }
}