二叉树的先序遍历

二叉树的先序遍历就是先遍历根节点，然后在遍历左节点，最后遍历右节点。

二叉树的遍历一般有两种实现：递归实现和非递归实现。其实递归实现和非递归实现的本质是一样的，两者都是利用了堆栈先进后出的原理来进行的。只是在递归的实现中，我们利用了系统方法调用时形成的堆栈，而非递归实现中，我们要自己来手动的实现堆栈元素的进出栈。

先序遍历

首先是递归实现

    public static void preTraversal(TreeNode root) {
if(root != null) {
            System.out.print(root.val + " ");
            preTraversal(root.left);
            preTraversal(root.right);
        } else {
return;
        }
    }

这个就没有什么好说的了，都看的懂

下面来说一下非递归实现。
首先上代码

    public static void preTraversalByStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root != null) {
stack.push(root);
        }

while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
if( node != null) {
                System.out.print(node.val + " ");
            }

if(node.right != null) {
stack.push(node.right);
            }

if(node.left != null) {
stack.push(node.left);
            }
        }
    }

按照图中的流程看来，每次根节点进站的时候都会把右子节点压入栈中，然后把左子节点压入栈中，左子节点入栈之后就立刻弹出，然后循环这个过程。

其实只看第一二步的出站顺序就可以很明显的看出来这个顺序就是根左右。所以我们实现递归的时候就是要利用堆栈来模拟根左右的这个过程。

中序遍历

递归实现的中序遍历

    public static void inTraversal(TreeNode root) {
if(root != null) {
            inTraversal(root.left);
            System.out.print(root.val + " ");
            inTraversal(root.right);
        } else {
return;
        }
    }

下面是非递归实现的中序遍历

public static void inTraversalByStack(TreeNode root) {
        Stack<TreeNode> treeNodes = new Stack<>();
while(root != null || !treeNodes.isEmpty()) {
while(root != null) {
                treeNodes.push(root);
                root = root.left;
            }

            root = treeNodes.pop();
            System.out.print(root.val + " ");

            root = root.right;
        }
    }

当我们开始中序遍历的时候，首先是开始找到树最左边的那个节点，在这之前所有的节点都应该压入栈中，找到了之后开始出栈，在出栈的时候开始处理右子树，处理右子树的方式又回到了前面说的，先找到最左边的节点，然后开始处理。

后序遍历

递归实现

public static void postTraversal(TreeNode root) {
if(root == null) {
return;
        } else {
            postTraversal(root.left);
            postTraversal(root.right);
            System.out.print(root.val + " ");
        }
    }

非递归实现

在非递归实现中，我们借用了两个栈，在第一个栈中，先将根元素入栈，然后出栈，出栈之后将其压入第二个栈，然后再将一个元素的左子树，右子树入第一个栈，然后依次再出栈，出栈的同时进入第二个栈，那么第二个栈的入栈顺序就是根，右，左，那么此时的第二个栈的出栈顺序就是左右根。

  public static void postTraversalByStack(TreeNode root) {
if(root == null) {
return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();

        stack1.push(root);

while(!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
if(node.left != null) {
                stack1.push(node.left);
            }

if(node.right != null) {
                stack1.push(node.right);
            }
        }

while(!stack2.isEmpty()) {
            TreeNode node = stack2.pop();
            System.out.print(node.val + " ");
        }

    }