二叉树的前序、中序、后序和层次遍历方法

前序遍历

/**
 * 递归实现
 * @param root
 * @return
 */
public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    preorderTraveralHelper(root, resultList);
    return resultList;
}

private static void preorderTraveralHelper(TreeNode root, List<Integer> list) {
    if(root == null)
        return;
    list.add(root.val);
    preorderTraveralHelper(root.left, list);
    preorderTraveralHelper(root.right, list);
}

/**
 * 利用栈的非递归实现
 * @param root
 * @return
 */
private static List<Integer> preorderTraveralIter(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    if(root == null)
        return list;
    while(root != null || !stack.isEmpty()) {
        if (root != null) {
            list.add(root.val);
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            //中序遍历：list.add(root.val);
            root = root.right;
        }
    }
    return list;
}

中序遍历

/**
 * 递归实现中序遍历; 非递归方法参考前序遍历
 * @param root
 * @return
 */
public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    inorderTraveralHelper(root, resultList);
    return resultList;
}

private static List<Integer> inorderTraveralHelper(TreeNode root, List<Integer> list) {
    if (root == null) 
        return list;
    inorderTraveralHelper(root.left, list);
    list.add(root.val);
    inorderTraveralHelper(root.right, list);
    return list;
}

后序遍历

/**
 * 递归实现后序遍历
 * @param root
 * @return
 */
public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    postorderTraveralHelper(root, resultList);
    return resultList;
}

private static List<Integer> postorderTraveralHelper(TreeNode root, List<Integer> list) {
    if (root == null) 
        return list;
    postorderTraveralHelper(root.left, list);
    postorderTraveralHelper(root.right, list);
    list.add(root.val);
    return list;
}

/**
 * 迭代法后序遍历
 * @param root
 * @return
 */
public static List<Integer> postorderTraversalIter(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    if (root == null) {
        return resultList;
    }
    TreeNode preNode = null;
    while(root != null || !stack.isEmpty()) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            TreeNode peekNode = stack.peek();
            //判断栈顶节点右节点是否为空或者已经被遍历过
            if (peekNode.right!=null && preNode!=peekNode.right) {
                root = peekNode.right;
            } else {
                stack.pop();
                preNode = peekNode;
                resultList.add(peekNode.val);
            }
        }

    }

    return resultList;
}

层次遍历

/**
 * 层次遍历二叉树并按层打印
 * @param root
 * @return
 */
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> resultList = new LinkedList<List<Integer>>();
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    if (root == null) {
        return resultList;
    }
    queue.offer(root);
    while(!queue.isEmpty()) {
        List<Integer> levelList = new ArrayList<Integer>(); 
        // poll current level and offer next level
        int num = queue.size();
        for (int i = 0; i < num; i++) {
            TreeNode top = queue.poll();
            System.out.println(top.val);
            levelList.add(top.val);
            // 必须判断是否为null，不然会将叶子节点的null子节点也加入队列，引起空指针错误
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
        resultList.add(levelList);
    }
    return resultList;
}