本文共 1748 字，大约阅读时间需要 5 分钟。

前言

二叉树的先、中、后序遍历是非常经典的面试题，作为基础算法面试题必须要掌握。

定义

假设有这么一棵二叉树

• 先序遍历：1、2、4、5、3、6、7（根-左-右）
• 中序遍历：4、2、5、1、6、3、7（左-根-右）
• 后序遍历：4、5、2、6、7、3、1（左-右-根）

代码实现

public class T_1 {
       List
   
     preList = new ArrayList<>();    List
    
      inList = new ArrayList<>();    List
     
       postList = new ArrayList<>();    public static void main(String[] args) {
           TreeNode t1 = new TreeNode(1);        TreeNode t2 = new TreeNode(2);        TreeNode t3 = new TreeNode(3);        TreeNode t4 = new TreeNode(4);        TreeNode t5 = new TreeNode(5);        TreeNode t6 = new TreeNode(6);        TreeNode t7 = new TreeNode(7);        t1.left = t2;        t1.right = t3;        t2.left = t4;        t2.right = t5;        t3.left = t6;        t3.right = t7;        T_1 t = new T_1();        t.preOrder(t1);        t.inOrder(t1);        t.postOrder(t1);        System.out.println(t.preList);        System.out.println(t.inList);        System.out.println(t.postList);    }    /**     * 先序遍历     *     * @param root     */    public void preOrder(TreeNode root) {
           if (root == null) {
               return;        }        preList.add(root.val);        preOrder(root.left);        preOrder(root.right);    }    /**     * 中序遍历     *     * @param root     */    public void inOrder(TreeNode root) {
           if (root == null) {
               return;        }        inOrder(root.left);        inList.add(root.val);        inOrder(root.right);    }    /**     * 后序遍历     *     * @param root     */    public void postOrder(TreeNode root) {
           if (root == null) {
               return;        }        postOrder(root.left);        postOrder(root.right);        postList.add(root.val);    }}
     
    
   

递归是非常简单的实现方式，根据先、中、后序遍历的不同，决定什么时候记录当前节点的值

转载地址：http://jelrb.baihongyu.com/