二叉树的三种遍历方式

概述

二叉树（Binary tree）是树形结构的一个重要类型。

许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。

当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

例子

前序遍历

思路

遍历顺序：根结点 -> 左子树 -> 右子树

代码示例

用递归的方式实现遍历。

package com.leetcode.editor.tree;

import com.leetcode.utils.TreeNode;

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

/**
 * 二叉树的前序遍历
 *
 * @author loquy
 * @date 2021 /12/10 16:32
 */
public class BinaryTreePreorderTraversal {

    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        TreeNode left2 = new TreeNode(4);
        TreeNode right2 = new TreeNode(5);
        TreeNode left = new TreeNode(2, left2, right2);
        TreeNode right3 = new TreeNode(6);
        TreeNode right = new TreeNode(3, null, right3);
        TreeNode treeNode = new TreeNode(1, left, right);
        List<Integer> integers = preorderTraversal(treeNode);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
        TreeNode.show(treeNode);
    }

    /**
     * Preorder traversal list.
     *
     * @param root the root
     * @return the list
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    /**
     * Preorder.
     *
     * @param root the root
     * @param res  the res
     */
    public static void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        // 前序遍历，根->左->右的顺序
        // 把当前节点的值添加到集合
        res.add(root.val);
        // 递归遍历左子树，直到没有左子树
        preorder(root.left, res);
        // 递归遍历右子树，直到没有右子树
        preorder(root.right, res);
    }
}

输出

1
2
4
5
3
6
      1      
    /   \    
  2       3  
 / \       \ 
4   5       6

中序遍历

思路

遍历顺序：左子树 -> 根结点 -> 右子树

代码示例

用递归的方式实现遍历。

package com.leetcode.editor.tree;

import com.leetcode.utils.TreeNode;

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

/**
 * 二叉树的中序遍历
 *
 * @author loquy
 * @date 2021 /12/06 10:25
 */
public class BinaryTreeInorderTraversal {

    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        TreeNode left2 = new TreeNode(4);
        TreeNode right2 = new TreeNode(5);
        TreeNode left = new TreeNode(2, left2, right2);
        TreeNode right3 = new TreeNode(6);
        TreeNode right = new TreeNode(3, null, right3);
        TreeNode treeNode = new TreeNode(1, left, right);
        List<Integer> integers = inorderTraversal(treeNode);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
        TreeNode.show(treeNode);
    }

    /**
     * Inorder traversal list.
     *
     * @param root the root
     * @return the list
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    /**
     * Inorder.
     *
     * @param root the root
     * @param res  the res
     */
    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            // 递归结束条件，空则返回
            return;
        }
        // 中序遍历，左->根->右的顺序
        // 递归遍历左子树，直到没有左子树
        inorder(root.left, res);
        // 把当前节点的值添加到集合
        res.add(root.val);
        // 递归遍历右子树，直到没有右子树
        inorder(root.right, res);
    }
}

输出

4
2
5
1
3
6
      1      
    /   \    
  2       3  
 / \       \ 
4   5       6

后序遍历

思路

遍历顺序：左子树 -> 右子树 -> 根结点

代码示例

用递归的方式实现遍历。

package com.leetcode.editor.tree;

import com.leetcode.utils.TreeNode;

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

/**
 * 二叉树的后序遍历
 * @author loquy
 * @date 2021/12/10 16:40
 */
public class BinaryTreePostorderTraversal {

    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        TreeNode left2 = new TreeNode(4);
        TreeNode right2 = new TreeNode(5);
        TreeNode left = new TreeNode(2, left2, right2);
        TreeNode right3 = new TreeNode(6);
        TreeNode right = new TreeNode(3, null, right3);
        TreeNode treeNode = new TreeNode(1, left, right);
        List<Integer> integers = postorderTraversal(treeNode);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
        TreeNode.show(treeNode);
    }

    /**
     * postorder traversal list.
     *
     * @param root the root
     * @return the list
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    /**
     * postorder.
     *
     * @param root the root
     * @param res  the res
     */
    public static void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        // 后序遍历，左->右->根的顺序
        // 递归遍历左子树，直到没有左子树
        postorder(root.left, res);
        // 递归遍历右子树，直到没有右子树
        postorder(root.right, res);
        // 把当前节点的值添加到集合
        res.add(root.val);
    }
}

输出

4
5
2
6
3
1
      1      
    /   \    
  2       3  
 / \       \ 
4   5       6

源码

查看此仓库

• 树类
• 前序
• 中序
• 后序