常考算法面试题系列：树的遍历

首文发布在 个人博客

两种通用的遍历树的策略

• DFS(深度优先遍历)：先序遍历，中序遍历，后序遍历；
• BFS(广度优先遍历)：层序遍历

深度优先遍历（DFS）

这种方法以深度 depth 优先为策略，从根节点开始一直遍历到某个叶子节点，而后回到根节点，在遍历另外一个分支。

根据根节点，左孩子节点和右孩子节点的访问顺序又可以将 DFS 细分为先序遍历 preorder，中序遍历 inorder 和后序遍历 postorder。

广度优先遍历（BFS）

按照高度顺序，从上往下逐层遍历节点。
先遍历上层节点再遍历下层节点。

下图中按照不同的方法遍历对应子树，得到的遍历顺序都是 1-2-3-4-5。根据不同子树结构比较不同遍历方法的特点。

图片来源leetcode题解

相关题目（leetcode）

DFS

先序遍历、中序遍历、后序遍历

1. 144. 先序遍历
   先序遍历为：根节点 -> 前序遍历左子树 -> 前序遍历右子树

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */var preorderTraversal = function(root) {    let result = [];    function pre (root) {        if(root !== null) {            // ① 根节点            result.push(root.val);            // ② 前序遍历左子树            pre(root.left);            // ③ 前序遍历右子树            pre(root.right);        }    }    pre(root);    return result;};

2. 94.中序遍历

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

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) {    let result = [];    function inorder(root) {        if(root != null) {            // ① 中序遍历左子树            inorder(root.left);            // ② 根结点            result.push(root.val);            // ③ 中序遍历右子树            inorder(root.right);        }    }    inorder(root);    return result;    };

3. 145.后序遍历
   后序遍历为：后序遍历左子树 -> 后序遍历右子树 -> 根结点

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */var postorderTraversal = function(root) {    const result = [];    function postorder(root) {        if(root!== null) {            // ① 后序遍历左子树            postorder(root.left);            // ② 后序遍历右子树            postorder(root.right);            // ③ 根结点            result.push(root.val);        }    }    postorder(root);    return result;};

根据两种遍历序列构造树

1. 106.从中序与后序遍历序列构造二叉树

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {number[]} inorder * @param {number[]} postorder * @return {TreeNode} */var buildTree = function (inorder, postorder) {    if (!inorder || inorder.length == 0) {        return null;    }    // 后序遍历的最后一个节点肯定是根节点    let treeNode = new TreeNode(postorder[postorder.length - 1]);    // 在中序遍历中找到 根节点的位置    let i = inorder.indexOf(postorder[postorder.length - 1]);    // 根据左子树的中序和后序遍历构建左子树    treeNode.left = buildTree(inorder.slice(0, i), postorder.slice(0, i));    // 根据右子树的中序和后序遍历构建右子树    treeNode.right = buildTree(inorder.slice(i + 1), postorder.slice(i, postorder.length - 1));    return treeNode;};

2. 105. 从前序与中序遍历序列构造二叉树

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */var buildTree = function(preorder, inorder) {    if (!inorder || inorder.length == 0) {        return null;    }    // 前序遍历的第一个节点肯定是根节点    let treeNode = new TreeNode(preorder[0]);     // 在中序遍历中找到 根节点的位置    let i = inorder.indexOf(preorder[0]);     // 根据左子树的前序和中序遍历构建左子树    treeNode.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));     // 根据右子树的前序和中序遍历构建右子树    treeNode.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));    return treeNode;};

3. 889. 根据前序和后序遍历构造二叉树

const constructFromPrePost = (pre, post) => {    const { length } = pre;    if (length === 0) return null;    // 前序遍历的第一个节点肯定是根节点    const root = new TreeNode(pre[0]);    // 在后序遍历中找到 根节点的位置    const index = post.indexOf(pre[1]);     // 根据左子树的前序和后序遍历构建左子树    root.left = constructFromPrePost(pre.slice(1, index + 2), post.slice(0, index + 1));    // 根据右子树的前序和后序遍历构建右子树    root.right = constructFromPrePost(pre.slice(index + 2, length), post.slice(index + 1, length - 1));      return root;  };

BFS

1. 102.层序遍历

按照高度顺序，从上往下逐层遍历节点。
先遍历上层节点再遍历下层节点。

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[][]} */var levelOrder = function(root) {    const result = [];    // level表示当前层级    function levelOrderNode(root, level) {        if(root!== null) {            if(result[level]) {                result[level].push(root.val)            } else {                result[level] = [root.val];            }            const nextLevel = level + 1;            levelOrderNode(root.left, nextLevel);            levelOrderNode(root.right, nextLevel);        }    }    levelOrderNode(root, 0);    return result; };

最后

这次看完应该了解了树的两种遍历策略了吧，假如还不懂，建议再看一遍，或者者自己去看leetcode相关的官方题解。