Java实现二叉树先序、中序、后序、层次遍历

一、二叉树数据结构

二叉树节点有：值（val）、左孩子（left）、右孩子（right）

class TreeNode{     //二叉树节点
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二、递归实现先序、中序、后序、层次遍历

• 先序遍历

List<Integer> preList = new ArrayList<Integer>();
public List<Integer> preOrder(TreeNode root) {        //先序遍历  递归
    if(root == null) {
        return null;
    }
    preList.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
    return preList;
}

• 中序遍历

List<Integer> inList = new ArrayList<Integer>();
public List<Integer> inOrder(TreeNode root){      //中序遍历   递归
    if(root == null)
        return null;
    inOrder(root.left);
    inList.add(root.val);
    inOrder(root.right);
    return inList;
}

• 后序遍历

List<Integer> postList = new ArrayList<Integer>();
public List<Integer> postOrder(TreeNode root){        //后序遍历   递归
    if(root == null)
        return null;
    postOrder(root.left);
    postOrder(root.right);
    postList.add(root.val);
    return postList;
}

• 层次遍历

private List<Integer> levelList = new ArrayList<>();
public void levelOrder(TreeNode root) {
    TreeNode node = root;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        node = queue.poll();
        levelList.add(node.val);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.rigth != null) {
            queue.offer(node.rigth);
        }
    }
}

三、迭代实现先序、中序、后序遍历

• 先序遍历

public List<Integer> preOrderStack(TreeNode root){    //先序遍历  迭代
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();      //栈
    TreeNode node = root;
    while((node != null) || !stack.empty()) {
        if(node != null) {                  //将左孩子压栈
            list.add(node.val);             //访问
            stack.push(node);
            node = node.left;
        }else {
            node = stack.pop();
            node = node.right;
        }
    }
    return list;
}

• 中序遍历

public List<Integer> inOrderStack(TreeNode root){     //中序遍历  迭代
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();      //栈
    TreeNode node = root;
    while((node != null) || !stack.empty()) {
        if(node != null) {                  //将左孩子压栈
            stack.push(node);
            node = node.left;
        }else {
            node = stack.pop();         //出栈并访问
            list.add(node.val);
            node = node.right;
        }
    }
    return list;
}

• 后序遍历

public List<Integer> postOrderStack(TreeNode root){       //后序遍历  迭代
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();      //栈
    Stack<TreeNode> output = new Stack<TreeNode>();     //构造一个中间栈，存储逆后序遍历的结果
    TreeNode node = root;
    while((node != null) || !stack.empty()) {
        if(node != null) {                  //将左孩子压栈
            output.push(node);          //保存节点，相当于前序遍历,根-右-左
            stack.push(node);
            node = node.right;
        }else {
            node = stack.pop();
            node = node.left;
        }
    }
    while(output.size() > 0) {
        node = output.pop();
        list.add(node.val);
    }
    return list;
}

四、测试

public static void main(String[] args) {
    BinaryTree binaryTree = new BinaryTree();
    TreeNode root = binaryTree.init();
    List<Integer> postList = binaryTree.postOrderStack(root); //后序遍历  迭代
    System.out.println(postList);       //结果：[4, 5, 2, 6, 7, 3, 1]
}

/**
 *    1
 *  2   3
 * 4 5 6 7
 */
public TreeNode init() {            //测试数据
    TreeNode node4 = new TreeNode(4, null, null);
    TreeNode node5 = new TreeNode(5, null, null);
    TreeNode node6 = new TreeNode(6, null, null);
    TreeNode node7 = new TreeNode(7, null, null);
    TreeNode node2 = new TreeNode(2, node4, node5);
    TreeNode node3 = new TreeNode(3, node6, node7);
    TreeNode node1 = new TreeNode(1, node2, node3);
    return node1;
}