面试题：二叉树的前中后序遍历

二叉树的前中后遍历，其前中后，您可理解为指的是根结点所在的序。

前序遍历：前序遍历的顺序为根-左-右
中序遍历：中序遍历的顺序为左-根-右
后序遍历：后序遍历的顺序为左-右-根
层次遍历: 从上到下，每一个层次从左到右

前序遍历

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Given a binary tree, return the preorder traversal of its TreeNodes' values.
 */
public class Lc144 {

    /*
     * 前序遍历 ：根左右 思路；将当前节点压入栈中，一直遍历左子树知道当前节点为空，向上弹出遍历一下右子树。
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            curr = curr.right;
        }
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 1, null, 2, null, null, 3 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<Integer> list = preorderTraversal(root);
        list.forEach(n -> System.out.println(n));
    }

}

中序遍历

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Given a binary tree, return the inorder traversal of its nodes' values.
 */
public class Lc94 {

    /*
     * 中序遍历：左根右
     */
    public static List<Integer> inOrderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> preorder = new ArrayList<Integer>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            preorder.add(curr.val);
            curr = curr.right;
        }
        return preorder;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 1, null, 2, null, null, 3 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<Integer> list = inOrderTraversal(root);
        list.forEach(n -> System.out.println(n));
    }

}

后续遍历

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Lc145 {

    /*
     * 后续序遍历：左右根
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        TreeNode curr = root;
        stack.push(curr);
        while (!stack.isEmpty()) {
            curr = stack.pop();
            list.add(0, curr.val);
            if (curr.left != null) {
                stack.push(curr.left);
            }
            if (curr.right != null) {
                stack.push(curr.right);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 0, 1, 2, 3, 4, 5, 6 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<Integer> list = postorderTraversal(root);
        list.forEach(n -> System.out.println(n));
    }

}

层序遍历

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Lc102 {

    /**
     * 层序遍历
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return lists;
        }

        TreeNode curr = root;
        queue.offer(curr);
        int size = queue.size();
        while (!queue.isEmpty()) {
            curr = queue.poll();
            list.add(curr.val);
            size--;
            if (curr.left != null) {
                queue.offer(curr.left);
            }
            if (curr.right != null) {
                queue.offer(curr.right);
            }
            if (size == 0) {
                lists.add(list);
                list = new ArrayList<>();
                size = queue.size();
            }

        }
        return lists;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 1, null, 2 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<List<Integer>> lists = levelOrder(root);
        lists.forEach(n -> {
            n.forEach(m -> {
                System.out.print(m + ",");
            });
            System.out.println();
        });

    }
}