1.一点感想

把java作为自己的主语言有一段时间了，大一上学期由于接触c51单片机从而自学了c语言的基础，下学期专业开了c语言的课，但是上课老师的讲课方式让我不是很能够适应，并且本人也在考虑以后毕业就业的事情，所以确定了java开发的一个道路。
为什么说二叉树是数据结构的灵魂呢？

竞赛类题目涉及大量的dfs,bfs,动态规划知识，并且这些算法大多能够通过递归的方式实现，而对于递归问题，我们首先要明确递归的退出条件，其次，我们还需要明确递归方法需要实现什么目的以及他对应需要的参数是什么。为了明确这些问题，我们可以手画递归树，从递归树明确我们每一步的操作，最后的运算，全部交给计算机就完了。这里面提到的“递归树”的概念，就是我们的二叉树。
一切数据结构归根到底都是有数组和链表来实现的。不管是队列、栈、树、图，都可以用这两个方式来实现 ```java Queue res=new LinkedList<>(); //链表实现队列

/ 用栈来实现队列 / class MyQueue { private Stack s1,s2;

public MyQueue() {
    s1=new Stack<>();
    s2=new Stack<>();
}
public void push(int x) {
    s1.push(x);
}
public int pop() {
    peek();
    return s2.pop();
}
public int peek() {
    if(s2.isEmpty()){
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
    }
    return s2.peek();
}
public boolean empty() {
    if(s1.isEmpty() && s2.isEmpty())
        return true;
    return false;
}

}

/ 用队列实现栈 / class MyStack { private Queue q; int topNum=0;; public MyStack() { q=new LinkedList<>(); }

public void push(int x) {
    q.offer(x);
    topNum=x;
}

public int pop() {
    int numsize=q.size();
    while(numsize>2){
        q.offer(q.poll());
        numsize--;
    }
    topNum=q.poll();
    q.offer(topNum);
    return q.poll();
}

public int top() {
    return topNum;
}

public boolean empty() {
    if(q.isEmpty())
        return true;
    return false;
}

}

我们的二叉树，同样可以通过这些方式进行有趣的改动：将二叉树序列化和反序列化，从遍历的序列结果来构造二叉树……并且，本人在做二叉树相关题目的时候，对递归的实现又有了比以前更深的了解。
<a name="gG4Yk"></a>
# 2.二叉树的遍历方式
<a name="PJtnO"></a>
## 1.[Leetcode144.二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
<a name="YI2iU"></a>
## 2.[Leetcode145.二叉树的后续遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
<a name="c5VVT"></a>
## 3.[Leetcode102.二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
解法答案：
```java
/*二叉树的后续遍历*/
class Solution {
    List<Integer> ans=new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        postreverse(root);
        return ans;
    }
    public void postreverse(TreeNode root){
        if(root==null)return;
        postreverse(root.left);
        postreverse(root.right);
        ans.add(root.val);
    }
}

/*二叉树的前序遍历*/
class Solution {
    List<Integer> ans=new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        pre(root);
        return ans;
    }
    public void pre(TreeNode root){
        if(root==null)return;
        ans.add(root.val);
        pre(root.left);
        pre(root.right);
    }
}



/*二叉树的层序遍历*/
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans=new LinkedList<>();
        Queue<TreeNode> res=new LinkedList<>();
        if(root==null){
            return ans;
        }
        res.add(root);
        while(!res.isEmpty()){
            int size=res.size();
            List<Integer> list=new LinkedList<>();
            for(int i=0;i<size;i++){
                TreeNode pre=res.poll();
                list.add(pre.val);
                if(pre.left!=null){
                    res.add(pre.left);
                }
                if(pre.right!=null){
                    res.add(pre.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }
}

相信做了这些题目以后，我们对递归的用法和二叉树遍历的框架有了了解！

4.框架

/*前序*/--根左右
PreorderTraversal(TreeNode root){
    if(root==null){
        return;
    }
    print(root.val);
    //这一行放对当前节点的操作，后面的递归调用会对对应节点进行同样的操作
    PreorderTraversal(root.left);
    PreorderTraversal(root.right);
}

/*后序*/--左右根
PostorderTraversal(TreeNode root){
    if(root==null){
        return;
    }
    print(root.val);
    PostorderTraversal(root.left);
    PostorderTraversal(root.right);
    //这一行放对当前节点的操作，后面的递归调用会对对应节点进行同样的操作
}

/*层序*/--从左到右从上到下
//一般我们用队列来实现层序遍历
levelorderTraversal(TreeNode root){
    Queue<TreeNode> q=new LinkedList<>();
    if(root==null){
        return null;
    }
    while(!q.isEmpty()){
        TreeNode tmp=q.poll();
        /*层序遍历代码位置*/
        if(q.left!=null){
            q.add(q.left);
        }
        if(q.right!=null){
            q.add(q.right);
        }
    }
    return q;
}

3.简单二叉树练习

1.Leetcode226.翻转二叉树

/*
思路非常明确，创建递归函数来进行反转。
有人可能会疑惑，示例一，二叉树只能对相同节点的子节点进行反转，那么怎么把不同节点的子树一样进行反转呢？其实并不需要考虑这个问题，我们把子节点反转==（等同于）把这个节点上的子树进行了翻转，按照递归基本的反转策略来说，完全可以达到题目的要求
*/

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;
    }
}

2.Leetcode116.填充每个结点的下一个右侧指针

/*仔细看完美二叉树的定义，这不就是满二叉树吗？！
至于题目要求的指针指向，我们创建一个递归函数实现指针指向下一个右侧节点的要求，根据这个要求，我们推测出我们需要传两个节点进去作为参数
对于上方的图3.1来看，首先对于root节点1，本身设置为1，而后调用connectNodeTwo,连接2和3，这个时候我们看第三层，思考：怎么做才能让不同父节点的子树进行指向呢？
很简单，首先把同一个子树的两个子节点进行连接，再把第一个子树的右节点和第二个子树的左节点连接起来就好了，也就是connectNodeTwo(t1.right,t2.left);
*/

class Solution {
    public Node connect(Node root) {
        if(root==null)return null;
        connectNodeTwo(root.left,root.right);
        return root;
    }

    public void connectNodeTwo(Node t1,Node t2){
        if(t1==null || t2==null)return;
        t1.next=t2;
        connectNodeTwo(t1.left,t1.right);
        connectNodeTwo(t2.left,t2.right);
        connectNodeTwo(t1.right,t2.left);
    }
}

3.Leetcode.114二叉树展开为链表

/*这个题目就有点难度了
仔细读题，题目要求顺序要和先序遍历相同，根据先序遍历的性质我们可以知道（根左右），左子树的节点总是在右子树的节点之上，因此，我们可以先断开root节点1的右子树，把左子树接到root上，然后再把右子树接到左子树后面，拼接的过程通过递归完成，所以我们子树拼接完以后自然就成为一条链表了（因为左分支都接到右分支的后面了）
*/

class Solution {
    public void flatten(TreeNode root) {
        if(root==null)return;
        flatten(root.left);
        flatten(root.right);
        TreeNode left=root.left;
        TreeNode right=root.right;
        root.left=null;
        root.right=left;
        TreeNode p=root;
        while(p.right!=null){    //找到将左子树拼接到root的右侧的最下方的节点，将这个节点的右节点连接到左子树的头节点
            p=p.right;
        }
        p.right=right;
    }
}

4.Leetcode.654最大二叉树

/*
题目的思路已经给我们了，在数组中找出最大值作为根节点，然后最大值左边的数组用同样的操作构建子树，右边类同
*/
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int low=0;
        int high=nums.length-1;
        return constructTree(nums,low,high);
    }
    public TreeNode constructTree(int[] nums,int low,int high){
        if(low>high){
            return null;
        }
        int index=-1;
        int max=Integer.MIN_VALUE;
        for(int i=low;i<=high;i++){
            if(nums[i]>max){
                max=nums[i];
                index=i;
            }
        }
        TreeNode root=new TreeNode(max);
        TreeNode left=constructTree(nums,low,index-1);
        TreeNode right=constructTree(nums,index+1,high);
        root.left=left;
        root.right=right;
        return root;
    }
}

4.进阶二叉树练习

我们知道二叉树的先序遍历顺序位：根左右
中序为：左根右
明确一点：知道前中后序遍历顺寻的任意其中两个，就能还原出一棵二叉树
我们可以知道preorder数组中的第一个元素3为二叉树的根节点，排在3后面的就是左子树区间和右子树区间。
再看中序遍历，找到3的位置，那么在inorder数组中3前面的就是左子树区间，3后面的就是右子树区间。
递归调用，参数是数组和数组的区间下标，递归的在里面查找我们需要的头节点和两个区间。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder,int prestart,int preend,
    int[] inorder,int instart,int inend){
        if(prestart>preend){
            return null;
        }
        int index=0;
        int rootnum=preorder[prestart];
        for(int i=instart;i<inorder.length;i++){
            if(inorder[i]==rootnum){
                index=i;
                break;
            }
        }
        int leftsize=index-instart;
        TreeNode root=new TreeNode(rootnum);
        root.left=build(preorder,prestart+1,leftsize+prestart,inorder,instart,index-1);
        root.right=build(preorder,prestart+leftsize+1,preend,inorder,index+1,inend);
        return root;
    }
}

有了这题作为参考，可以去试试Leetcode.106从中序和后续遍历序列构造二叉树

2.Leetcode652.寻找重复的子树

怎么样在一棵二叉树中寻找重复的子树？
不妨设想我们是怎么在一个数组中寻找重复的数字的？找到一个数字，记录他的数值为1，若再次找到，则数值加1，最后输出数值不为1的数就行了。这题，我们同样可以这么想，只需要一个小小的步骤：序列化！
将二叉树序列化以后，利用hashmap来确定子树的数量，键：子树的序列化结果，值：出现的次数，初始为0.

class Solution {
    HashMap<String,Integer> ans=new HashMap<>();
    List<TreeNode> res=new LinkedList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }
    public String traverse(TreeNode root){        // 序列化及将结果添加进hashmap集合
        if(root==null){
            return "#";
        }
        String left=traverse(root.left);
        String right=traverse(root.right);
        String tmp=left+","+right+","+root.val;     //按后序遍历序列化
        int freq=ans.getOrDefault(tmp,0);
        if(freq==1){
            res.add(root);
        }
        ans.put(tmp,freq+1);
        return tmp;
    }
}

3.Leetcode297.二叉树的序列化与反序列化

public class Codec {     //前序遍历
    StringBuilder sb=new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        traverse(root);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> list=new LinkedList<>();
        for(String s:data.split(",")){
            list.add(s);
        }
        return retraverse(list);
    }

    public void traverse(TreeNode root){
        if(root==null){
            sb.append("null").append(",");
            return;
        }
        sb.append(root.val).append(",");
        serialize(root.left);
        serialize(root.right);
    }

    public TreeNode retraverse(LinkedList<String> ls){
        if(ls.isEmpty())return null;
        String rootnum=ls.removeFirst();
        if(rootnum.equals("null"))return null;
        TreeNode root=new TreeNode(Integer.parseInt(rootnum));
        root.left=retraverse(ls);
        root.right=retraverse(ls);
        return root;
    }
}

public class Codec {        //后续遍历
    StringBuilder sb=new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        traverse(root);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> list=new LinkedList<>();
        for(String s:data.split(",")){
            list.add(s);
        }
        return retraverse(list);
    }

    public void traverse(TreeNode root){
        if(root==null){
            sb.append("null").append(",");
            return;
        }
        traverse(root.left);
        traverse(root.right);
        sb.append(root.val).append(",");
    }

    public TreeNode retraverse(LinkedList<String> ls){
        if(ls.isEmpty())return null;
        String last=ls.removeLast();
        if(last.equals("null")){
            return null;
        }
        TreeNode root=new TreeNode(Integer.parseInt(last));
        root.right=retraverse(ls);
        root.left=retraverse(ls);
        return root;
    }
}

算法入门

数据结构的灵魂：从二叉树入手