二叉树遍历

前序遍历

中-左-右

private void print(Node x){
    if(x == null) return;
    sout(x.key)
    print(x.left);
    print(x.right);
}

中序遍历

左-中-右

private void print(Node x){
    if(x == null) return;
    print(x.left);
    sout(x.key);
    print(x.right);
}

后续遍历

左-右-中

private void print(Node x){
    if(x == null) return;
    print(x.left);
    print(x.right);
    sout(x.key);
}

层序遍历(基本)--实质就是广度优先算法

如此遍历二叉树（美团面试题）

图

官渡

输出结果： 1 2 3 4 5 6 7 8 9 10

要点：

使用队列先进先出的特性； 父节点->左子节点->右子节点： 依次放入队列中； 从队列中取出元素N，将N的左右子节点依次放入队列

xx

层序遍历（变种）

变种

输出结果： 1 3 2 4 5 6 10 9 8 7

要点：

使用 双栈 实现

xx

zz

yyxx