二叉树的前中后序遍历——本质（每个节点都是“根”节点）

重点是自己要做一下题

在二叉树的遍历的三种方法中
根-左-右
左-根-右
左-右-根
记住每个节点都是根
所以前序遍历的时候，会先“忽略”右子树
中序遍历的时候，不会先打印 上一个根的左子树（因为可能上一个根的左子树，也是其它节点的根）
后续遍历的时候，把每个根遍历完，才能打印出根节点

注意：每次遍历到的节点，其实都是根节点

1.前序遍历（每次遍历的节点都先当做根）

2. 中序遍历（只有把根的左子树遍历完，再打印根）

3. 后序遍历（只有把左右子树都遍历完，再打印根）

1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
2. LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
3. LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点

前序遍历结果：1 2 3 4 5 6（每次遍历的节点都先当做根）
中序遍历结果：3 2 1 5 4 6（只有把根的左子树遍历完，再打印根）
后序遍历结果：3 1 5 6 4 1（只有把左右子树都遍历完，再打印根）

    // 前序遍历
    void preOrder(TreeNode root) {
    
        if(root == null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
    
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
    
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }