先序遍历

首先遍历根节点，然后在遍历左子树，最后在遍历右子树。

上述二叉树的先序遍历顺序如下:

1->2->4->5->3->6->7

递归实现：

public static void preOrder(Node root){
    if (root==null){
        return;
    }
    //先访问根节点
    System.out.print(root.val);
    //递归遍历左子树
    //递归遍历右子数
    preOrder(root.left);
    preOrder(root.right);
}

非递归实现：

//非递归实现先序遍历
public static void preOrderNoR(TreeNode root){
    if (root==null){
        return;
    }
    //创建一个栈
    Stack<TreeNode> stack=new Stack<>();
    //将根节点入栈
    stack.push(root);
    while(!stack.isEmpty()){

        TreeNode cur=stack.pop();
        System.out.print(cur.val);
        if (cur.right!=null){
            //因为栈是后进先出，而先序遍历时右子树是最后被访问的，所以先将右子树压栈，再将左子树压栈
            stack.push(cur.right);
        }
        if (cur.left!=null){
            stack.push(cur.left);
        }
    }
}

中序遍历

首先遍历左子树，再遍历根节点，最后遍历右子树。

上述的二叉树中序遍历顺序如下：

4->2->5->1->6->3->7

递归实现：

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

非递归实现：

//非递归中序遍历
public static void inOrderNoR(TreeNode root){
    if (root==null){
        return;
    }
    Stack<TreeNode> stack=new Stack<>();
    TreeNode cur=root;
    while(true){
        //往栈中插入元素
        while (cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        if (stack.isEmpty()){
            //栈为空则代表已经遍历完毕，然后跳出循环
            break;
        }
        //栈不为空则取出栈顶元素进行访问
        TreeNode top=stack.pop();
        System.out.print(top.val);
        //让cur指向右子树并继续进行上述操作
        cur=top.right;
    }
}

后序遍历

首先遍历左子树，再遍历右子树，最后遍历根节点。

上述二叉树后序遍历顺序如下：

4->5->2->6->7->3->1

递归实现：

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

非递归实现：

//非递归后序遍历
public static void postOrderNoR(TreeNode root){
    if (root==null){
        return;
    }
    Stack<TreeNode> stack=new Stack<>();
    TreeNode cur=root;
    //记录后序遍历的前一个节点
    TreeNode prev=null;
    while (true){
        //让cur出发一直往左走，遇到非空节点都入栈
        while (cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        //栈为空则跳出循环
        if (stack.isEmpty()){
            break;
        }
        //访问栈顶元素
        TreeNode top=stack.peek();
        //如果当前节点的右子树不为空，并且prev也不是他的右子树，则prev就是他的左子树
        if (top.right==null||prev==top.right){
            System.out.print(top.val);
            stack.pop();
            prev=top;
        }else {
            //如果访问不了那么就从他的右子树出发
            //重复上述过程
            cur=top.right;
        }
    }
}