二叉树的遍历

我们知道知道
前序遍历 + 中序遍历 --------------- 可以确定唯一一棵二叉树
后序遍历 + 中序遍历 --------------- 可以确定唯一一颗二叉树
前序遍历 + 后序遍历 --------------- 不能唯一确定

！因为先序后序遍历都是确定根的位置，但不能确定左右子树的位置，一颗二叉树的建立需要根的位置也需要左右子树的位置。

练习链接:
从前序与中序遍历构造二叉树
从中序与后序遍历构造二叉树

根据前序遍历和中序遍历重建二叉树

首先来看下这两种遍历的方式， 前序遍历的遍历是：根节点 – 左子树 – 右子树 , 中序遍历是 左子树 – 根节点 – 右子树. 故前序遍历的第一个节点必然是二叉树的根节点， 来看上面二叉树的前序遍历 :
a - b - d - e - c - f - g; 故可以确定a就是二叉树的根节点。 然后我们在中序遍历中找到a这个节点。
d - b - e - (a) - f - c - g; 根据中序遍历先遍历左子树，再遍历根节点最后遍历右子树的这个特点，我们就知道了中序遍历中a的左边 d b e 是a的左子树部分， 因为中序遍历必定先遍历完根节点的左子树部分再遍历根节点， 故a的右边部分 f c g 就是a的右子树部分。 故接下来的过程就是找到a的左子树节点和a的右子树节点， 故a的左子树节点必然在中序遍历的 a 左边的部分， a 的右子树节点必定在中序遍历的a的右半部分, 以找a左子树节点为例子，此时我们知道了其左子树就是 d - b - e， 这三个节点， 而再看前序遍历， 前序遍历要先遍历根节点再遍历左子树， 故前序遍历中a后面的三个节点即为左子树的三个节点，其第一个节点即为左子树根节点。故b为a的左子树节点，同样我们以b为根节点的子树在中序遍历找到b的位置， 其位置为 d - （b） - e - a - f - c - g; 其左边为只有一个d为其左子树，右边只有一个e为其右子树。 同样找a右子树的时候， 由中序遍历知道了 f - c - g 是 a 的右子树， 故在前序遍历中知道了第一个是根节点a, 又知道其先遍历了3个左子树节点，故第五个节点开始遍历右子树，其第五个节点就是右子树的根节点。 以此递归，看下面的代码实现

/*
这里并没有专门写一个类或者结构体，表示一个节点(包括存放的数据和左右子树的指针)
直接用map表示每一个节点的左子树是那个节点和右子树是那个节点. 
*/
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
constexpr int N = 40;
int pre[N], in[N];
unordered_map<int, int> l, r, pos;

int Recstr_Tree(int il, int ir, int pl, int pr)
{
    int root = pre[pl];            // 可知前序遍历最先遍历根节点
    int k = pos[root];             // pos用 map快速找到根节点在中序遍历的位置 
    
    // 若il < k，即中序遍历的左边界小于当前根节点在中序遍历的节点位置，说明该根节点存在左子树, 进行递归
    // 故此时递归时, 左边子树的中序范围为 il ~ k - 1, 前序遍历的左边界要向前移动故 pl + 1, 然后前序的
    // 右边界如何确定， 可得 (k - 1) - il = x - (pl + 1)  -->  x = pl + k - il;
    if(il < k) l[root] = Recstr_Tree(il, k - 1, pl + 1, pl + k - il);   


    if(ir > k) r[root] = Recstr_Tree(k + 1, ir, pl + k - il + 1, pr);
    
    return root;          
} 

// 层序遍历 
auto level_traversal(int root)
{
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int node = q.front(); q.pop();
        cout << node << " ";
        if(l[node]) q.push(l[node]);
        if(r[node]) q.push(r[node]);
    }
}

auto main() -> int
{
    int n; cin >> n;
    for(int i = 0; i < n; ++i) cin >> pre[i];    // 输入前序遍历
    for(int i = 0; i < n; ++i)
    {
        cin >> in[i];                           // 输入中序遍历
        pos[in[i]] = i;                         // 保存每个节点在中序遍历的位置
    }
    int root = Recstr_Tree(0, n - 1, 0, n - 1); // 重建树
    level_traversal(root);                      // 进行层序遍历
    cout << endl;
    return 0;
}

根据后序遍历和中序遍历重建二叉树

相关题目的链接 ： AcWing 1497. 树的遍历

同样的话根据后序遍历 和 中序遍历重建二叉树也是同理，后序遍历是先遍历左子树 – 遍历右子树 – 最后遍历根节点， 故每次确定根节点应该是用后序遍历的右边界来确定， 故代码实现基本差不多 .

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
constexpr int N = 40;
int post[N], in[N];
unordered_map<int, int> l, r, pos;

int Recstr_Tree(int il, int ir, int pl, int pr)
{
    int root = post[pr];
    int k = pos[root];
    if(il < k) l[root] = Recstr_Tree(il, k - 1, pl, pl + k - il - 1);
    if(ir > k) r[root] = Recstr_Tree(k + 1, ir, pl + k - il, pr - 1); 
    return root;
}

auto level_traversal(int root)
{
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int node = q.front(); q.pop();
        cout << node << " ";
        if(l[node]) q.push(l[node]);
        if(r[node]) q.push(r[node]);
    }
}

auto main() -> int
{
    int n; cin >> n;
    for(int i = 0; i < n; ++i) cin >> post[i]; 
    for(int i = 0; i < n; ++i)
    { 
        cin >> in[i]; 
        pos[in[i]] = i;
    }
    int root = Recstr_Tree(0, n-1, 0, n-1);
    level_traversal(root);
    cout << endl;
    return 0;
}

两道题目的答案

前序 + 中序

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    unordered_map<int, int> pos; 
    TreeNode* Rcstr(vector<int>& preorder, vector<int>& inorder, int il, int ir, int pl, int pr)
    {
        TreeNode *root = new TreeNode(preorder[pl]); 
        int k = pos[preorder[pl]]; 

        if(il < k) root->left = Rcstr(preorder, inorder, il, k - 1, pl + 1, pl + k - il);  
        if(k < ir) root->right = Rcstr(preorder, inorder, k + 1, ir, pl + k - il + 1 ,pr); 
        return root; 
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int n = inorder.size();
        for(int i = 0; i < n; ++i) pos[inorder[i]] = i; 
        TreeNode *root = Rcstr(preorder, inorder, 0, n - 1, 0, n - 1); 
        return root;
    }
};

后序 + 中序

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    unordered_map<int, int> pos; 
    TreeNode* Rcstr(vector<int> &inorder, vector<int> &postorder, int il, int ir, int pl, int pr)
    {
        TreeNode *root = new TreeNode(postorder[pr]); 
        int k = pos[postorder[pr]]; 

        if(il < k) root->left = Rcstr(inorder, postorder, il, k - 1, pl, pl + k - il - 1); 
        if(k < ir) root->right = Rcstr(inorder, postorder, k + 1, ir, pl + k - il, pr - 1);

        return root; 
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        int n = inorder.size(); 
        for(int i = 0; i < n; ++i) pos[inorder[i]] = i; 
        TreeNode *res = Rcstr(inorder, postorder, 0, n - 1, 0, n - 1); 
        return res; 
    }
};

根据层序遍历和中序遍历重建二叉树

如何通过层序遍历序列和中序遍历序列来确定一棵二叉树？

• 根据层序遍历序列第一个结点确定根结点；
• 根据根结点在中序遍历序列中分割出左右子树的中序序列；
• 根据分割出的左右子树的中序序列从层序序列中提取出对应的左右子树的层序序列；
• 对左子树和右子树分别递归使用相同的方式继续分解；

层序遍历的一个特点就是其第一个节点表示的是根节点, 但是其本身的层序遍历的序列并没有按照一定的顺序, 如前面的前序遍历和后序遍历都是按照一定的顺序, 根 -> 左子树 -> 右子树 / 左子树 -> 右子树 -> 根。故我们可以很容易的写出其递归方程, 但是这里的层序遍历我们唯一能够确认的是其第一个必定是整棵二叉树的根节点. 所以根据这个条件我们每次遍历的时候都要重新构建其中左子树和右子树的层序序列, 以此来确定其左右子树的根节点.

具体实现

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;  

unordered_map<int, int> pos; 

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(vector<int>& levelorder, vector<int>& inorder) 
{
    int n = levelorder.size();
    TreeNode *root = new TreeNode(levelorder[0]);
    cout << "n = " << n << "  val = " << root->val << endl; 
    int k = pos[levelorder[0]];           // 其中 pos 为快速找到对应元素在中序遍历中的位置 
    vector<int> left_level, right_level;  // 记录左右子树的层序遍历
    
    // 重新构建左右子树的层序遍历 
    // 中序遍历确定左右子树个数 
    // 然后根据现有的层序遍历的顺序来构建左右子树的层序序列  
    
    for(int i = 0; i < n; ++i) 
    {
        for(int j = 0; j < k; ++j) 
            if(levelorder[i] == inorder[j]) left_level.push_back(inorder[j]);
        for(int c = k + 1; c < inorder.size(); ++c)
            if(levelorder[i] == inorder[c]) right_level.push_back(inorder[c]);
    }
    
    if(left_level.size())  root->left = buildTree(left_level, inorder); 
    if(right_level.size()) root->right = buildTree(right_level, inorder); 
    return root;
}

一.根据一棵树的前序遍历与中序遍历构造二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路

首先我们可以知道通过前序遍历和中序遍历，就可以知道整个二叉树的结构了。然后自上而下的深度递归构造。

代码

private int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        index=0;
        return  buildTreeHelper(preorder,inorder,0,inorder.length);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        //空树
        if(left>=right){
            return null;
        }
        //遍历完
        if(index>=preorder.length){
            return null;
        }
        //根据当前根节点的值创建出根节点
        TreeNode root=new TreeNode(preorder[index]);
        index++;
        //中序遍历数组中找到root的位置
        int pos=find(inorder,left,right,root.val);
        //左子树是root在中序遍历结果中的左边的节点
        root.left=buildTreeHelper(preorder,inorder,left,pos);
        //同理，右子树是root在中序遍历结果中的右边的节点，记得要pos+1
        root.right=buildTreeHelper(preorder,inorder,pos+1,right);
        return root;
    }
    
    //查找出root在中序遍历数组中的位置
    private int find(int[] inorder, int left, int right, int toFind) {
        //遍历查找
        for (int i = left; i < right; i++) {
            if(inorder[i]==toFind){
                return i;
            }
        }
        //没找到按理不存在（一定能找到）
        return -1;
    }

二.根据一棵树的中序遍历与后序遍历构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。

思路

首先一定要先看懂我上面的前序遍历和中序遍历构造二叉树(这个理解之后，那么这题就很简单了)，看图

所以我们只需要逆置一下二叉树的后序遍历，那么就得到前序遍历的镜像了，根右左。所以就转换成了前序遍历和中序遍历二叉树的问题了。构造左右的时候只需要注意，先构造右，，再构造左即可，其余代码一模一样。

代码

private int index=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index=0;
        //逆置后序遍历数组
        reverse(postorder);
        return  buildTreeHelper(postorder,inorder,0,inorder.length);
    }
    //因为后序遍历，逆置一下，就是先序遍历的镜像，根右左
    //这样就转化成 先序与中序遍历构造二叉树的问题了（只是要注意左右子树顺序）
    private void reverse(int[] postorder) {
        int left=0;
        int right=postorder.length-1;
        //交换
        while (left<right){
            int tmp=postorder[left];
            postorder[left]=postorder[right];
            postorder[right]=tmp;
            left++;
            right--;
        }
    }

    private TreeNode buildTreeHelper(int[] postorder, int[] inorder, int left, int right) {
        //空树
        if(left>=right){
            return null;
        }
        //遍历完
        if(index>=postorder.length){
            return null;
        }
        //根据当前根节点的值创建出根节点
        TreeNode root=new TreeNode(postorder[index]);
        index++;
        int pos=find(inorder,left,right,root.val);
        //代码和前序遍历与中序遍历构造二叉树一样
        //只是需要注意改动一下左右构造的顺序即可
        //代码不做详细注解了，不懂的可以看前序和中序构造二叉树的代码注释(基本一模一样)
        root.right=buildTreeHelper(postorder,inorder,pos+1,right);
        root.left=buildTreeHelper(postorder,inorder,left,pos);
        return root;
    }

    private int find(int[] inorder, int left, int right, int toFind) {
        for (int i = left; i < right; i++) {
            if(inorder[i]==toFind){
                return i;
            }
        }
        return -1;
    }

有人可能会问，为啥没有前序遍历和后序遍历构造二叉树的题呢？
嘿嘿嘿，首先通过遍历构造二叉树，一定要知道两种遍历结果，并且中序遍历一定要存在，不然无法确定二叉树的结果哦。

二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现

提示：今天开始，系列二叉树的重磅基础知识和大厂高频面试题就要出炉了，咱们慢慢捋清楚！

文章目录

• 二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
• • @[TOC](文章目录)
• 二叉树
• 二叉树的递归先序、中序、后序遍历
• 递归序：二叉树递归必定要3次见面
• 二叉树的非递归先序、中序、后序遍历
• • 非递归先序遍历
  • 非递归后序遍历
  • 非递归中序遍历
• 总结

二叉树

啥是二叉树？
就是双指针，只向下指的，无环的链表

二叉树的节点：

public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }

一颗合格的二叉树，无环，往下指，只有2个指针，【多个指针就是多叉树了，比如前缀树】

叶节点的左右指针全是null
造一颗二叉树：

//构造一颗树，今后方便使用
    public static Node generateBinaryTree(){
        //树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        Node head = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        head.left = n2;
        head.right = n3;
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n2.left = n4;
        n2.right = n5;
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        n3.left = n6;
        n3.right = n7;
        return head;
    }

关于二叉树，咱们可有得说了，
要学二叉树的遍历，包括先序，中序，后序，按层遍历，
这些有可用递归实现，和非递归实现
后面我们还要学二叉树的序列化，反序列化
寻找二叉树的后继节点、前驱节点
树形动态规划DP：二叉树的递归套路
各种关于二叉树的知识点……

二叉树的递归先序、中序、后序遍历

先序遍历：打印顺序是头、左、右
中序遍历：打印顺序是左、头、右
后序遍历：打印顺序是左、右、头

比如：

先序遍历：1 2 4 5 3 7 8
中序遍历：4 2 5 1 7 3 8
后序遍历：4 5 2 7 8 3 1

三者的递归函数遍历打印函数很简单：
先打印头，然后是左树，然后是右树

//先序遍历打印
    public static void prePrint(Node head){
        if(head == null) return;//不管是头还是叶节点，这就是递归的终止条件
        //先打印头，再打印左子树，再打印右子树
        System.out.print(head.value +" ");
        prePrint(head.left);
        prePrint(head.right);
    }
    //中序遍历打印
    public static void inPrint(Node head){
        if(head == null) return;
        //中序遍历，先打印左边，再打印头，再打印右边
        inPrint(head.left);
        System.out.print(head.value +" ");
        inPrint(head.right);
    }
    //后序遍历打印
    public static void postPrint(Node head){
        if(head == null) return;
        //后序遍历打印，先打印左边，再打印右边，最后打印头
        postPrint(head.left);
        postPrint(head.right);
        System.out.print(head.value +" ");
    }

测试一波：

public static void test(){
        Node cur = generateBinaryTree();
        prePrint(cur);
        System.out.println();
        inPrint(cur);
        System.out.println();
        postPrint(cur);
    }
    public static void main(String[] args) {
        test();
//        test2();
    }

看结果：

**1** 2 4 5 3 6 7 
4 2 5 **1** 6 3 7 
4 5 2 6 7 3 **1** 

递归序：二叉树递归必定要3次见面

递归序：调用递归函数f(head)
一定要三次与head见面

递归，首先来到节点1，然后去左子树，
左子树首先见到节点2，然后去左子树，
左子树首先见到节点4，然后去左子树，见到null，返回
再次见到4，再去4的右子树，见到null，返回
再次见到4，然后返回，再次见到2，然后去2的右子树，
首次见到5，然后去5的左子树，见到null，返回
再次见到5，然后去5的右子树，见到null，返回
再次见到5，然后返回，再次见到2，
返回，再次见到1，去1的右子树，见到3
去3的左子树，见到6，去6的左子树，见到null返回再次见到6，
去6的右子树，见到7，去7的左子树，null，返回，再次见到7
去7的右子树，见到null，返回再次见到7，返回再次见到6，
再返回，再次见到1,
递归到此结束

发现，每一个节点，f都会访问它3次。
先序遍历：第一次见面就打印
中序遍历：第二次见面打印
后序遍历：第三次见面打印

//左神汇总一波理解这个遍历的问题
    //树长啥样呢
    //          1
    //        2   3
    //       4 5 6 7
    //递归序：递归总会走这么一个顺序，每一个节点都会遇见3次：
    //走：1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,6,7,7,7,3,1
    //每一个点：首先来到头遇到第一次，然后去左边访问回来又遇见一次，然后去右边访问回来在遇见一次，3次
    //第一次遇到一个点，打印它：则先序遍历
    //第二次遇到一个点，打印它，则中序遍历
    //第三次遇到一个点，打印它，则后续遍历
    //总结：也就是先，中，后，三种遇见打印叫先中后序的遍历；
    public static void f(Node head){
        if(head == null) return;
        //第一次遇见就打印的话，先序遍历
        //System.out.print(head.value +" ");
        f(head.left);
        //第二次遇见打印的话，中序遍历
        //System.out.print(head.value +" ");
        f(head.right);
        //第三次遇见打印的话，后序遍历
        System.out.print(head.value +" ");
    }

    public static void test2(){
        Node cur = generateBinaryTree();
        f(cur);

    }
    public static void main(String[] args) {
        test();
//        test2();
    }

你分别注释打印的位置，
就能得到结果。

二叉树的非递归先序、中序、后序遍历

任何递归实现的代码，都能通过非递归实现
既然是一个遍历的事情
就可以让栈来实现
当节点x，出来访问时，它左子右子可以陆续压栈，由于栈能先进后出，所以压入的顺序，决定了弹出的顺序
从而达到控制x的左子和右子打印的顺序
（1）如果遇到x打印，然后先压右子，再压左子，弹出时，必定先弹出左子，再弹出右子
这不就是头、左、右吗？——先序遍历

（2）如果遇到x打印，然后先压左子，再压右子，弹出时，必定先弹出右子，再弹出左子
这不就是头、右、左吗？
此时，你再逆序一下：左、右、头——后序遍历
巧了吧？

（3）关于中序遍历，比较复杂，但是也就是用栈巧妙地控制进出栈的顺序
咱们这么想
我们中序遍历打印顺序是左，头，右
那么先让头别打印
A：我们先压头x，然后去x的左树操作，不断地，压头，继续去左树
然后遇到null后，返回，打印左
然后打印头，然后去右树压x，继续循环A
这样的话，打印顺序就是左、头、右
在代码中，就是控制if else条件，进入左树和右树【这玩意死记硬背，记不了算了】

非递归先序遍历

自己手撕代码撕清楚

//复习（1）如果遇到x打印，然后先压右子，再压左子，弹出时，必定先弹出左子，再弹出右子
    //这不就是头、左、右吗？——先序遍历
    public static void unRecurrentPrePrint(Node head){
        if (head == null) return;

        Stack<Node> stack = new Stack<>();
        stack.push(head);//先压头
        while (!stack.isEmpty()){
            //首先打印头
            Node cur = stack.pop();
            System.out.print(cur.value + " ");
            //然后反着压，先压右边，再压左边，回头就是左右顺序出
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
    }

1 2 4 5 3 6 7 

非递归后序遍历

自己想清楚思想，然后手撕代码

//复习：（2）如果遇到x打印，然后先压左子，再压右子，弹出时，必定先弹出右子，再弹出左子
    //这不就是头、右、左吗？
    //此时，你再逆序一下：左、右、头——后序遍历
    public static void unRecurrentPostPrint(Node head){
        if (head == null) return;

        //俩栈，一个控制压入顺序，一个控制逆序
        Stack<Node> inStack = new Stack<>();
        Stack<Node> backStack = new Stack<>();
        inStack.push(head);//先入头，再入左右--逆序放入back：头右左，输出左右头
        while (!inStack.isEmpty()){
            Node cur = inStack.pop();
            backStack.push(cur);//逆序放

            if (cur.left != null) inStack.push(cur.left);//先左
            if (cur.right != null) inStack.push(cur.right);//后右--出去就是头右左，back才能是左右头
        }

        //逆序输出
        while (!backStack.isEmpty()){
            System.out.print(backStack.pop().value +" ");//back才能是左右头
        }
    }

非递归中序遍历

//这样的话，打印顺序就是左、头、右
    public static void unRecurrentInPrint(Node head){
        if (head == null) return;

        Stack<Node> stack = new Stack<>();
        //只要是左边不空，去左树
        while (!stack.isEmpty() || head != null){
            //为啥要加head呢？？
            if (head != null) {
                //先左树
                stack.push(head);
                head = head.left;//可能就去遇到了null
            }else {
                //如果左树是null，head是叶节点
                //说明树的第一个左叶节点该打印了，然后去打印头，再去右树
                head = stack.pop();
                System.out.print(head.value +" ");
                head = head.right;
            }
        }
    }

测试一下：

public static void test2(){
        //造树
        Node head = generateBinaryTree1();
        //先序
        unRecurrentPrePrint(head);
        System.out.println();
        //后序
        unRecurrentPostPrint(head);
        System.out.println();
        //中序
        unRecurrentInPrint(head);

    }


    public static void main(String[] args) {
//        test();
        test2();
    }

1 2 4 5 3 6 7 先序
4 5 2 6 7 3 1 后序
4 2 5 1 6 3 7 中序

总结

提示：重要经验：

1）递归序，3次见面，第一次见面打印叫先序遍历，第二次见面打印叫中序遍历，第三次见面打印叫后序遍历
2）非递归实现中，先序和后序是相反的，但是中序遍历挺难理解，但是核心思想也就是先去左树，再打印头，然后再去右树。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。