先序 中序 后序的区别与联系

• 先序是对每一个节点来说，都是 头 左 右 的顺序
• 中序是对每一个节点来说，都是 左 头 右 的顺序
• 后序是对每一个节点来说，都是 右 头 左 的顺序

而无论是先序中序还是后序，都可以看作是递归序的子集

递归序

啥是递归序呢，先看如下 的一个递归结构

    public static void f(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val+" ");
        f(root.left);
        System.out.print(root.val+" ");
        f(root.right);
        System.out.print(root.val+" ");
    }

如果记录每一次到达每个节点的情况，那么现在有这么一棵树

那么最后的输出结果就为[2 1 1 1 2 4 3 3 3 4 4 2]可以看出每一个节点出现了三次。

递归序可以简单看成，

头节点2先去左树，得到1，【2，1】

1的左树啥也没，回到1，【2，1，1】

1的右树啥也没，回到1，【2，1，1，1】

然后回到2，【2，1，1，1，2】

2的右树得到4，【2，1，1，1，2，4】

……

就得到这个递归序

从递归序转换为其他

每一个节点都出现了三次，假如将每一个节点第一次出现的顺序挑出来

那么就是先序：[2 1 4 3]

每一个节点的第二次为中序[1 2 3 4]

每一个节点的第三次就是后序[1 3 4 2]

只需要去调整输出语句的位置，就可以完成

• 先序

    public static void f(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val+" ");
        f(root.left);
        f(root.right);
    }

• 中序

    public static void f(TreeNode root){
        if (root==null){
            return;
        }
        f(root.left);
        System.out.print(root.val+" ");
        f(root.right);
    }

• 后序

    public static void f(TreeNode root){
        if (root==null){
            return;
        }
        f(root.left);
        f(root.right);
        System.out.print(root.val+" ");
    }

leetCode的一些题

题目一：二叉树的中序遍历

这个要求返回一个链表，可以在递归外定义一个类变量，在原来输出的位置替换成链表的add

    List<Integer> ans = new LinkedList<>();
    public  void f(TreeNode root){
        if (root==null){
            return;
        }
        f(root.left);
        ans.add(root.val);
        f(root.right);
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        f(root);
        return ans;
    }

题目二：二叉树的先序遍历

    List<Integer> ans = new LinkedList<>();
    public  void f(TreeNode root){
        if (root==null){
            return;
        }
        ans.add(root.val);
        f(root.left);
        
        f(root.right);
    }
    public List<Integer>  preorderTraversal(TreeNode root) {
        f(root);
        return ans;
    }

题目三：二叉树的后序遍历

    List<Integer> ans = new LinkedList<>();
    public  void f(TreeNode root){
        if (root==null){
            return;
        }
        f(root.left);
        f(root.right);
        ans.add(root.val);
    }
    public List<Integer>  postorderTraversa(TreeNode root) {
        f(root);
        return ans;
    }