二叉树遍历

数据结构

    private static class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

深度优先&广度优先

深度优先：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。深度优先遍历非递归的通用做法是采用栈。
广度优先：从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。广度优先遍历使用方法为层次遍历，非递归的通用做法是采用队列

先序遍历

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。按照这个规则，可以很容易的写出先序遍历的递归方法。

 /**
     * 先序遍历二叉树，递归
     * @param root
     */
    public static void preOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraverse(root.left);
        preOrderTraverse(root.right);
    }

对于非递归方法，可以描述为：由根节点开始，不断将二叉树的节点压入栈中，然后由栈中取出栈顶节点，并且将该节点的右、左（顺序不可颠倒）子节点压入栈中，循环此过程直至栈为空。 该方法的java代码如下：

/**
     * 先序遍历二叉树，非递归
     * @param root
     */
    public static void preOrderTraverseNoRecursion(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode currentNode = stack.pop();
            System.out.print(currentNode.val + " ");
            if (currentNode.right != null){
                stack.push(currentNode.right);
            }
            if (currentNode.left != null){
                stack.push(currentNode.left);
            }
        }
        System.out.print("\n");
    }

中序遍历

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。按照这个规则，可以很容易的写出中序遍历的递归方法。

 /**
     * 中序遍历二叉树，递归
     * @param root
     */
    public static void inOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }
        inOrderTraverse(root.left);
        System.out.print(root.val + " ");
        inOrderTraverse(root.right);
    }

后序遍历

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后再访问根。按照这个规则，可以很容易的写出后序遍历的递归方法。

 /**
     * 后序遍历二叉树，递归
     * @param root
     */
    public static void postOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }
        postOrderTraverse(root.left);
        postOrderTraverse(root.right);
        System.out.print(root.val + " ");
    }

层次遍历

层次遍历指的是将二叉树按层输出。借助队列可以很容易的实现层次优先遍历。算法描述为：由根节点开始，不断将二叉树的节点送至队列中，然后由队列中取出队列头节点，并且将该节点的左、右子节点分别送至队列中，循环此过程直至队列为空。java代码如下：

 /**
     * 普通层次遍历
     * @param root
     */
    public static void levelTraverse(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode currentNode = queue.poll();
            System.out.print(currentNode.val + " ");
            if (currentNode.left != null){
                queue.add(currentNode.left);
            }
            if (currentNode.right != null){
                queue.add(currentNode.right);
            }
        }
        System.out.println();
    }

//层次遍历进阶
//除了一般的层次遍历，这里再介绍一种面试中常考的层次遍历——按二叉树的层次结构分行输出元素。要实//现这种需求，只需要两个指针记录当前行和下一行最右的节点即可。java代码如下：
 /**
     * 按行打印二叉树
     * 算法描述：
     * 1. 初始化：将根节点传入队列，last、nlast指针均指向根节点，
     *    其中，last指针指向当前行最右侧的元素，nlast指针指向下一行最右侧的元素
     * 2. 循环判断队列是否为空，如果不为空，则：
     *    2.1: 获取队列头元素p（将其在队列内删除）并打印
     *    2.2: 将该节点的左右子树分别压入队列，并更新nlast指针
     *    2.3: 判断last指针与p是否相等，如果相等，则换行，并且更新last = nlast
     * @param root
     * @return
     */
    public static void printTreeByRow(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        
        TreeNode last = root;
        TreeNode nLast = null;
        
        while (!queue.isEmpty()){
            TreeNode p = queue.poll();
            System.out.print(p.val + " ");

            if (p.left != null){
                queue.add(p.left);
                nLast = p.left;
            }
            if (p.right != null){
                queue.add(p.right);
                nLast = p.right;
            }
            // 当last == p时代表该换行了
            if(last == p){
                last = nLast;
                System.out.print("\n");
            }
        }
    }