二叉树遍历Java(递归+迭代)：前序、中序和后续遍历（双栈法+Deque法）

先根遍历、中根遍历和后根遍历

核心思维模型：对于二叉树的遍历，首先要将 Base Case 具体化出来，最底层的子节点不是没有左、右两个子节点，应该将其左、右两个子节点用 null 表示出来。即最底层子节点的左、右子节点都是 null。

在每次递归遍历中，该子节点相对于本次遍历都是一个根节点，它的左右子节点即使都是null，也是有左右子节点的！对于递归方法，最底层子节点和一个普通的根节点没有任何区别。

先根遍历递归 Pre-Order Traversal

深度优先遍历 - 前序遍历： F, B, A, D, C, E, G, I, H.

public void preOrder(BinaryTreeNode root) {
    //Base Case
    if(root == null) return;
    System.out.print(root.value);
    //遍历左子树
    preOrder(root.left);
    //遍历右子树
    preOrder(root.right);
复制代码

先根遍历迭代

深入优先遍历二叉树需要借助栈结构来实现。

* 先根遍历迭代法 public List<Integer> preOrderTraversal (BinaryTreeNode root) { List<Integer> list = new ArrayList<>(); if (root == null) return list; Stack<BinaryTreeNode> stack = new Stack<>(); //第一步：将根节点压入栈中 stack .push (root); BinaryTreeNode curNode; while (!stack.isEmpty()) { //第二步：将根节点弹出栈，并将值加入List集合，根节点遍历完成 curNode = stack .pop (); list .add (curNode.value); //第三步：根据深度优先搜索二叉树的先根遍历规则，需要先遍历左子树，然后才是右子树 //结合栈的FILO 先入后出原则，先压右子节点，再压左子节点。 //当再次循环弹出顶部元素时，最先弹出的就是左子节点，此时由于是深入优先，所以右子 //节点继续乖乖呆在栈底待命，直到左子树所有节点都入栈并出栈之后，最后才弹出第一次 //压入栈底的右子节点，最后才是对右子树进行遍历。 if (curNode.right != null) { stack .push (curNode.right); //第四步：压入左子节点到栈顶，等待下一次循环时首先弹出得到遍历 if (curNode.left != null) { stack .push (curNode.left); return list; 复制代码

中根遍历递归 In-Order Traversal

深度优先遍历 - 中根遍历： A, B, C, D, E, F, G, H, I.

public void inOrder(BinaryTreeNode root) {
    if(root == null) return;
    inOder(root.left);
    System.out.print(root.value);
    inOder(root.right);
复制代码

中根遍历迭代法

public List<Integer> inOrderTraversal(BinaryTreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode curNode = root;
        while(!stack.isEmpty() || curNode != null) {
            //这一部分实现了递归添加左节点的作用。
            //首先遍历左子节点，包括根节点都入栈，由于是中序遍历，所以根节点在左子树全部
            //节点出栈完毕之后跟着出栈，然后根节点的右子树再走一遍这个相同循环流程
            while(curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            //这一部分实现了对根节点的遍历，同时将指针指向了右子树，在下轮中遍历右子树。
            //每次出栈即遍历完一个节点，需要把当前节点的指针移动到右子节点，不管当前节点
            //的右子节点是否为null。如果是null，下次循环就直接走到出栈流程，把当前节点的
            //根节点弹出（此处以左子节点为例：根节点早于左子节点入栈），此时该
            //根节点刚好有右子节点，指针移动到右子节点，接着继续执行相同的循环。直到当前
            //节点和栈都为空，表明遍历结束。
            if(!stack.isEmpty()) {
                curNode = stack.pop();
                list.add(curNode.value);
                curNode = curNode.right;
        return list;
复制代码

后根遍历递归 Post-Order Traversal

深度优先搜索 - 后序遍历： A, C, E, D, B, H, I, G, F.

public void postOrder(BinaryTreeNode root) {
    if(root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.value);
复制代码

后根遍历迭代法（双栈法）

* 参考：https://segmentfault.com/a/1190000016674584? utm_medium =referral&utm_source=tuicool * 仔细观察一下后序遍历的顺序：左 -- 右 -- 根 * 根节点在最后，对照先序遍历的顺序：根 -- 左 -- 右 * 这里我们可以想到，将先序遍历微调为：根 -- 右 -- 左的顺序，这个微调很简单，只是在push节点到栈 * 里时，先push左节点，再push右节点，此时栈顶是右节点，那么下次循环就会先弹出右节点，此时， * 再把弹出的右节点push到反向栈 stackReverse 里即可。 * 核心：我们只需要增加一个栈来反向输出微调之后的先序遍历的每个节点，就可以得到后序遍历顺序。 public List<Integer> postOrderTraversal(BinaryTreeNode root) { List<Integer> list = new ArrayList<>() ; if ( root == null) return list ; Stack<BinaryTreeNode> stack = new Stack<>() ; Stack<BinaryTreeNode> stackReverse = new Stack<>() ; stack.push(root) ; BinaryTreeNode curNode ; while (!stack.isEmpty()) { curNode = stack.pop() ; stackReverse.push(curNode) ; if (curNode.left != null) { stack.push(curNode.left) ; if(curNode.right != null) { stack.push(curNode.right) ; while(!stackReverse.isEmpty()) { curNode = stackReverse.pop() ; list.add(curNode.value) ; return list ; 复制代码

注意：由于双栈法使用了额外的栈空间，也增加了一个循环，还可以优化。

后根遍历迭代法（使用Deque，即双向队列法）

* 双向队列法和先序遍历迭代的区别只是使用了 Deque 这种链表数据结构，每次都 * 从链表头插入新节点。由于 LinkedList 本身已经实现了 Deque 接口和List接口，因此 * LinkedList 可以作为一个双向队列来使用，同时本身也是List的实现类。可以很方便地 * 实现将新节点插入到表头的需求。 public List<Integer> postOrderTraversalByDeque(BinaryTreeNode root) { LinkedList<Integer> resultList = new LinkedList<>() ; if ( root == null) return resultList ; Stack<BinaryTreeNode> stack = new Stack<>() ; stack.push(root) ; BinaryTreeNode curNode ; while(!stack.isEmpty()) { curNode = stack.pop() ; resultList.addFirst(curNode.value) ; if (curNode.left != null) { stack.push(curNode.left) ; if (curNode.right != null) { stack.push(curNode.right) ; return resultList ; 复制代码