[Java]前中后序遍历二叉树/递归与非递归

一、递归方法

首先，树形结构都是由递归方式定义的。那么递归是怎么用的？

1、终止条件；2、调用自身

分析

1、什么时候停止？

当结点值为空的时候，返回null；

2、如何调用自身？

以前序遍历为例：前序遍历的顺序是——根节点、左节点、右节点

先打印根节点，然后打印经过前序遍历的左子树，最后打印经过前序遍历的右子树

其他两种遍历方法同理

前序遍历

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

中序遍历

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

 后序遍历

public void postOrder(TreeNode root){//后序遍历
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val + " ");
    }

二、非递归方法

分析

因为树形结构都是由递归方式定义的，所以非递归方法就是用其他方法来模拟递归。

我们要通过栈中的结点才能从其左节点遍历到右节点。

我这里使用的是栈，当然也可以使用其他结构

前序遍历

以深度为2的二叉树举例：

1、将根节点A入栈，打印A，cur指向cur.left

 2、将cur指向的结点cur入栈，并打印B。cur指向左节点，此时cur为空。

3、此时左节点已经遍历完毕，开始遍历右节点。弹出栈顶元素并设为top，使得cur等于top，cur移向右节点 。此时对于cur指向的B结点来说左子树为空，右子树也为空。说明B结点已经遍历完了。

 4、上一个栈顶元素已经左右子树遍历完了。此时再弹出栈顶元素，开始遍历其右子树。cur指向top

5、如果此时top的右边有结点，则将其入栈。

 6、cur指向其左边，查看是否有左子树。cur = cur.left

7、左侧为空则开始遍历其右子树。弹出栈顶元素，cur = top 。然后cur = cur.right

8、 发现右侧为空，且栈为空。遍历结束

代码如下

public void preOrderNor(TreeNode root){
        //模拟遍历的终止条件
        if (root == null){
            return;
        }
        TreeNode cur = root;
        Deque stack = new ArrayDeque<>();
        //如果指针cur不为空且栈中还有元素，说明遍历未结束
        while (cur != null || !stack.isEmpty()){
            //如果cur不为空，将其入栈（用以和其右子树产生联系）并打印，然后查看其左子树，
            //直到左子树为空
            while (cur != null){
                stack.push(cur);
                System.out.println(cur.val + " ");
                cur = cur.left;
            }
            //此时左子树为空，弹出栈顶元素开始遍历其右子树
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

中序遍历与后序遍历同理

中序遍历

public void inOrderNor(TreeNode root){
        if (root == null){
            return;
        }
        TreeNode cur = root;
        Deque stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(cur.val + " ");
            cur = top.right;
        }
    }

 后序遍历

public void postOrderNor(TreeNode root){
        if (root == null){
            return;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //此时左子树已经遍历完了，但是还不能弹出栈顶元素。
            //因为这是后续遍历，根节点要在右结点打印后才能打印
            //现在弹出去后面就没法打印这个根节点了
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev){
                System.out.println(top.val + " ");
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
        System.out.println();
    }