前言

二叉树是面试官非常喜欢考察的数据结构，面试中非常常见，今天来讲解一下二叉树的遍历，深度优先。其中递归遍历方式较为简单，大家可以尝试非递归如何实现。

树

在数据结构中，树是一种非线性的数据结构。

• 节点：树中的基本元素，包含数据信息。
• 根节点：树中最顶层的节点，一棵树只有一个根节点。
• 子节点：一个节点的直接下属节点。
• 父节点：一个节点的直接上级节点。
• 叶子节点：没有子节点的节点。
• 分支：节点之间的连接关系。
• 层次：从根节点开始计算，根节点为第一层，根节点的子节点为第二层，以此类推。
• 树的高度：从根节点到最深叶子节点的最长路径长度（边数）。

用js表示

function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

二叉树

二叉树是树结构的一种特殊形式。

二叉树是每个节点最多有两个子树的树结构。这两个子树有左右之分，分别被称为左子树和右子树。

• 节点的度不超过 2，即节点最多有两个分支。
• 二叉树可以为空，即没有节点。
• 左子树和右子树也是二叉树。
• 二叉树具有有序性，即左右子树是有明确区分的。

用js表示

function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

// 根节点val1
const node = new TreeNode(1)

const node2 = new TreeNode(2)
const node3 = new TreeNode(3)

// 左子节点val2
node.left = node2

// 右子节点val3
node.right = node3

用对象来表示一个二叉树

const root = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        }
        , right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: null,
        right: {
            val: 6,
            left: null,
            right: null
        }
    }
}

二叉树的遍历（深度遍历）

先序遍历（根左右）

先序遍历是二叉树的一种遍历方式，其遍历顺序是先访问根节点，再递归遍历左子树，最后递归遍历右子树。

1. 访问根节点
2. 递归地先序遍历左子树
3. 递归地先序遍历右子树

先序遍历的实现

function preorder(root) {
    if (!root) return;
    console.log(root.val);

    // root.left
    preorder(root.left);
    // root.right
    preorder(root.right);
}

preorder(root)

中序遍历（左根右）

其遵循的顺序是“左-根-右”，即先遍历左子树，然后访问根节点，最后遍历右子树。中序遍历常用于二叉查找树（Binary Search Tree, BST），因为它会以升序方式返回树中的元素。

1. 递归地遍历左子树。
2. 访问当前节点（根节点）。
3. 递归地遍历右子树。

中序遍历的实现

function inorder(root) {
    if (!root) return;
    // root.left
    inorder(root.left);
    console.log(root.val);
    // root.right
    inorder(root.right);
}

inorder(root)

后序遍历（左右根）

其访问顺序遵循“左-右-根”的原则，即先遍历左子树，然后遍历右子树，最后访问根节点。

1. 递归地遍历左子树。
2. 递归地遍历右子树。
3. 访问当前节点（根节点）

后序遍历的实现

function lastorder(root) {
    if (!root) return;
    // root.left
    lastorder(root.left);
    // root.right
    lastorder(root.right);
    console.log(root.val);
}
lastorder(root)

leetcode145实战 （后序递归遍历）

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

 

示例 1：

输入： root = [1,null,2,3]
输出： [3,2,1]

示例 2：

输入： root = []
输出： []

示例 3：

输入： root = [1]
输出： [1]

 

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    const res = [];
    const afo = (root) => {
        if (!root) return;
        afo(root.left)
        afo(root.right)
        res.push(root.val)
    }
    afo(root)
    return res;
};

leetcode94实战（中序递归遍历）

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

 

示例 1：

输入： root = [1,null,2,3]
输出： [1,3,2]

示例 2：

输入： root = []
输出： []

示例 3：

输入： root = [1]
输出： [1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var inorderTraversal = function (root) {
    const res = []
    const ino = (root) => {
        // 左 中 右
        if (!root) return;
        ino(root.left)
        res.push(root.val)
        ino(root.right)
    }
    ino(root)
    return res;
};

leetcode144实战（附前序非递归遍历）

给你二叉树的根节点 root ，返回它节点值的 前序 **遍历。 示例 1：

输入： root = [1,null,2,3]
输出： [1,2,3]

示例 2：

输入： root = []
输出： []

示例 3：

输入： root = [1]
输出： [1]

示例 4：

输入： root = [1,2]
输出： [1,2]

示例 5：

输入： root = [1,null,2]
输出： [1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶： 递归算法很简单，你可以通过迭代算法完成吗？

递归：

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const res = [];
    const preo = (root)=>{
        if (!root) return;
        res.push(root.val);
        preo(root.left);
        preo(root.right);
    }
    preo(root)
    return res;
};

非递归实现方式（迭代法）

• 前序遍历是中左右，如果用栈来存储，因为栈先进后出的特性，就需要先存右再存左
• 排除空树的情况

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    if (!root) return [];
    const res = []
    const stack = []
    stack.push(root)

    while (stack.length) {
        const cur = stack.pop()
        res.push(cur.val)
        if (cur.right) {
            stack.push(cur.right)
        }
        if (cur.left) {
            stack.push(cur.left)
        }
    }


    return res
};

小结

以上主要讲解了二叉树的深度优先遍历，先序遍历，中序遍历，后序遍历的递归以及非递归的方式做遍历。

事实上二叉树的遍历，除了深度优先遍历的先中后序遍历，还有广度优先遍历的层序遍历大家可以去leetcode102自行尝试。