二叉树递归遍历，程序员必备技能！

创作时间:

2025-01-21 22:57:18

作者:

@小白创作中心

二叉树递归遍历，程序员必备技能！

二叉树的递归遍历是每位程序员必须掌握的基础技能之一。无论是前序遍历、中序遍历还是后序遍历，都能帮助我们在解决复杂问题时游刃有余。本文将详细介绍二叉树递归遍历的各种方法，让你轻松掌握这一重要技巧。无论是在面试中还是日常开发工作中，这些知识都将是你不可或缺的工具。快来一起学习吧！

二叉树的基本概念

在深入学习递归遍历之前，我们先来了解一下二叉树的基本概念。二叉树是一种数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树可以为空，也可以由一个根节点和两个互不相交的子树组成，这两个子树本身也是二叉树。

二叉树中的节点可以包含以下信息：

节点值（val）
左子节点指针（left）
右子节点指针（right）

在JavaScript中，二叉树节点的定义如下：

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

在Go语言中，二叉树节点的定义如下：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

递归遍历详解

递归遍历是处理二叉树的一种常用方法，它通过函数调用自身来访问树中的每个节点。根据访问根节点的顺序不同，递归遍历可以分为前序遍历、中序遍历和后序遍历。

前序遍历（Preorder Traversal）

前序遍历的顺序是“根节点 -> 左子树 -> 右子树”。具体步骤如下：

访问根节点
递归遍历左子树
递归遍历右子树

前序遍历的代码实现如下：

function preorderTraversal(root) {
    if (root === null) {
        return;
    }
    console.log(root.val); // 访问根节点
    preorderTraversal(root.left); // 遍历左子树
    preorderTraversal(root.right); // 遍历右子树
}

中序遍历（Inorder Traversal）

中序遍历的顺序是“左子树 -> 根节点 -> 右子树”。具体步骤如下：

递归遍历左子树
访问根节点
递归遍历右子树

中序遍历的代码实现如下：

function inorderTraversal(root) {
    if (root === null) {
        return;
    }
    inorderTraversal(root.left); // 遍历左子树
    console.log(root.val); // 访问根节点
    inorderTraversal(root.right); // 遍历右子树
}

后序遍历（Postorder Traversal）

后序遍历的顺序是“左子树 -> 右子树 -> 根节点”。具体步骤如下：

递归遍历左子树
递归遍历右子树
访问根节点

后序遍历的代码实现如下：

function postorderTraversal(root) {
    if (root === null) {
        return;
    }
    postorderTraversal(root.left); // 遍历左子树
    postorderTraversal(root.right); // 遍历右子树
    console.log(root.val); // 访问根节点
}