1. 二叉树中序遍历

给一棵树，输出中序遍历。
树已经给你建好了，按照一下形式：

/**
 * 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,null,2,3]
输出：[1,3,2]

（1）递归实现：（俺的，耗时长）

class Solution {
     List<Integer> list = new ArrayList<Integer>();
    void show_mid(TreeNode r){
        if(r==null) return ;
        if(r!=null){
            show_mid(r.left);
            list.add(r.val);
            show_mid(r.right);
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        //输入先序，输出中序
        show_mid(root);
        return list;
    }
}

（2）栈
按照：右子节点、自身、左子节点依次入栈，访问后做标记。

想要这样输出：
前序遍历：中，左，右
中序遍历：左，中，右
后序遍历：左，右，中
就要倒着入栈。

public List<Integer> inorderTraversal(TreeNode root){
    List<Integer> res = new ArrayList<>();
    Deque<Object> stack = new LinkedList<>();
    if(root == null) return res;
    stack.push("WHITE");
    stack.push(root);
    while(!stack.isEmpty()){
       TreeNode node = (TreeNode)stack.pop();
       String color = (String)stack.pop();
       if (node == null) continue;
       if(color == "WHITE"){
           stack.push("WHITE");
           stack.push(node.right);
           stack.push("GRAY");
           stack.push(node);
           stack.push("WHITE");
           stack.push(node.left);
       }else{
           res.add(node.val);
       }
    }
    return res;
}

2.二叉树的最大深度

求树的高度
递归求数高度（不够快）

class Solution {
    int get_height(TreeNode t){
        if(t==null){
            return 0;
        }
        return Math.max(get_height(t.left),get_height(t.right))+1;
    }
    public int maxDepth(TreeNode root) {
        return get_height(root);

    }
}

108. 将有序数组转换为平衡二叉搜索树

你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡二叉搜索树。

class Solution {
    TreeNode create(int[] a,int l,int r){
        if(l>r) return null;
        TreeNode t=new TreeNode();
        int mid=(l+r)/2;
        t.val=a[mid];
        t.left=create(a,l,mid-1);
        t.right=create(a,mid+1,r);
        return t;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        //建立平衡二叉树，返回树
        //数组已经排好序了，直接利用它建树
        //中间为根，左边为左子树，右边为右子树
        return create(nums,0,nums.length-1);
    }
}

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

这题关键点在于：是整个树的镜像，所以先左右子树交换，再一步步往下进行交换【先交换后递归】。

class Solution {
    void inverse(TreeNode t){
        if(t==null) return ;
        TreeNode temp;
        temp=t.left;
        t.left=t.right;
        t.right=temp;
        inverse(t.left);
        inverse(t.right);
    }
    public TreeNode invertTree(TreeNode root) {
        //返回树
        //由于是一整个镜像，所以从头开始就将左右两个子树翻转
        inverse(root);
        return root;

    }
}

二叉树层序遍历

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
重点在于要一层层分出来

用levelEnd记录每层最后一个节点的编号，注意上一层最后的节点与这层最后节点没有直接关系，所以要用数组中front指代的点。
（明明难度是简单，但我做了好久。）

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> listALL = new ArrayList<List<Integer>>();
        
        //再层序遍历时换需要标记处在哪开始下一层
        TreeNode[] qu=new TreeNode[2050];
        int front=0,base=0;
        int levelEnd=0;
        if(root==null) return listALL;
        qu[front++]=root;//先把根节点放进去
        int k=0;//用来记录ListALL里的第一个list
        listALL.add(new ArrayList<Integer>());
        while(front>base){
            TreeNode t=qu[base++];
            // System.out.println(t.val);
            listALL.get(k).add(t.val);

            if(t.left!=null) qu[front++]=t.left;
            if(t.right!=null) qu[front++]=t.right;
            if(base-1==levelEnd){
                //当前为层末尾
                // for (Integer s: list1) {
                //     System.out.print(s);
                // }
                //  System.out.println();
                listALL.add(new ArrayList<Integer>());//层list放List里
                levelEnd=front-1;//记住当前末尾节点在数组里的位置
                 System.out.println(levelEnd);
                 k++;
            }
        }
        if(listALL.get(k).isEmpty()) listALL.remove(listALL.get(k));//把最后一个空的[]移除
        return listALL;

    }
}

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
关键点：将一棵树的判断对称，转变成两棵树，一颗的左枝叶对应另一颗右枝叶。

class Solution {
    boolean Isame(TreeNode t1,TreeNode t2){
        if(t1==null&&t2==null) return true;//全为空 T
        if(t1==null||t2==null) return false;//其中一个为空 F
        if(t1.val==t2.val) {
            if(Isame(t1.left,t2.right)&&Isame(t1.right,t2.left)) 
                return true;
            else return false;
        }
        return false;
        
       
    }
    public boolean isSymmetric(TreeNode root) {
        return Isame(root,root);
    }
}

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
关键在于：本质就是遍历所有的点，找到以每个节点为根时左右子树的长度之和，送这些和中找maxx

//我的第一种写法：
//将找长度和遍历所有点分开，遍历使用先序遍历
class Solution {
    int maxx=-1;
    int getHeight(TreeNode t){
        //当前结点为根下最长的两个叶子，那一定在左右枝分别取到
        if(t==null) return 0;
        return Math.max(getHeight(t.right),getHeight(t.left))+1;
    }
    void showFirst(TreeNode t){
        if(t==null) return ;
        int l=0,r=0;
        if(t.left!=null){
            l=getHeight(t.left);
        }
        if(t.right!=null){
            r=getHeight(t.right);
        }
        if((l+r)>maxx) maxx=(l+r);

        showFirst(t.left);
        showFirst(t.right);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        //两边的点决定的路径肯定有公共根节点
        //记录-以当前结点为根节点深度最深的两个叶子的深度之和，从记录中找到最长的
        
        //遍历每个树节点——先序遍历
        showFirst(root);
        return maxx;
    }
}

简化版，将遍历左右子树长度和，结合在一个函数中。

class Solution {
    int maxx=-1;
    int getHeight(TreeNode t){
        //当前结点为根下最长的两个叶子，那一定在左右枝分别取到
        if(t==null) return 0;
        //分别得到左右子树长度
        int l=getHeight(t.left);
        int r=getHeight(t.right);
        System.out.println(l+"+"+r);
        if((l+r)>maxx) maxx=(l+r);
        return Math.max(l,r)+1;//返回长度
    }
    
    public int diameterOfBinaryTree(TreeNode root) {
        int a = getHeight(root);
        return maxx;
    }
}

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
输入：root = [3,1,4,null,2], k = 1
输出：1

class Solution {
    int x=-1,cnt=0;
    void search(TreeNode t,int k){
        if(t==null) return ;
        search(t.left,k);
        cnt++;
        if(cnt==k) x=t.val;

        search(t.right,k);
    }
    public int kthSmallest(TreeNode root, int k) {
        //二叉搜索树，左小右大
        //中序遍历从小到大
        search(root,k);
        return x;

    }
}

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

class Solution {
    void cenEnd(TreeNode r){
        
    }
    public List<Integer> rightSideView(TreeNode root) {
        //右视图就是每层最后一个点，从头到尾放到list里
        //与我之前写的层序遍历类似
    List<Integer> list = new ArrayList<Integer>();
        TreeNode[] qu = new TreeNode[201];
        int front=0,base=0,levelEnd=0;
        if(root==null) return list;
        qu[front++]=root;
        while(front>base){
            TreeNode t=qu[base++];
            if(t.left!=null) qu[front++]=t.left;
            if(t.right!=null) qu[front++]=t.right;
            if(levelEnd==(base-1)){
                list.add(t.val);
                levelEnd=front-1;
            }
        }
        return list;

    }
}

105. 从前序与中序遍历序列构造二叉树

定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历,inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

就是根据先序遍历和中序遍历建树。

class Solution {
    TreeNode create1(int[] preorder,int[] inorder){//前 中
        if(preorder.length<=0) return null;
        TreeNode t = new TreeNode();
        t.val=preorder[0];
        int i,len=preorder.length;
        for(i=0;i<len;i++){
            if(inorder[i]==preorder[0]) break;
        }
        t.left=create1(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
        t.right=create1(Arrays.copyOfRange(preorder,i+1,len),Arrays.copyOfRange(inorder,i+1,len) );//左闭右开的数组切片
        return t;

    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return create1(preorder,inorder);

    }
}