嘲芈保考算法面試題系列：樹的遍歷

首文發(fā)布在個人博客

兩種通用的遍歷樹的策略

DFS(深度優(yōu)先遍歷)：先序遍歷弊决，中序遍歷，后序遍歷魁淳；
BFS(廣度優(yōu)先遍歷)：層序遍歷

深度優(yōu)先遍歷（DFS）

這種方法以深度 depth 優(yōu)先為策略飘诗，從根節(jié)點開始一直遍歷到某個葉子節(jié)點，然后回到根節(jié)點界逛，在遍歷另外一個分支昆稿。

根據(jù)根節(jié)點，左孩子節(jié)點和右孩子節(jié)點的訪問順序又可以將 DFS 細(xì)分為先序遍歷 preorder息拜，中序遍歷 inorder 和后序遍歷 postorder溉潭。

廣度優(yōu)先遍歷（BFS）

按照高度順序，從上往下逐層遍歷節(jié)點少欺。
先遍歷上層節(jié)點再遍歷下層節(jié)點喳瓣。

下圖中按照不同的方法遍歷對應(yīng)子樹，得到的遍歷順序都是 1-2-3-4-5赞别。根據(jù)不同子樹結(jié)構(gòu)比較不同遍歷方法的特點畏陕。

圖片來源leetcode題解

相關(guān)題目（leetcode）

DFS

先序遍歷、中序遍歷仿滔、后序遍歷

144. 先序遍歷
先序遍歷為：根節(jié)點 -> 前序遍歷左子樹 -> 前序遍歷右子樹

/**
 * 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) {
            // ① 根節(jié)點
            result.push(root.val);
            // ② 前序遍歷左子樹
            pre(root.left);
            // ③ 前序遍歷右子樹
            pre(root.right);
        }
    }
    pre(root);
    return result;
};

94.中序遍歷

中序遍歷為：中序遍歷左子樹 -> 根結(jié)點 -> 中序遍歷右子樹

/**
 * 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);
            // ② 根結(jié)點
            result.push(root.val);
            // ③ 中序遍歷右子樹
            inorder(root.right);
        }
    }
    inorder(root);
    return result;
    
};

145.后序遍歷
后序遍歷為：后序遍歷左子樹 -> 后序遍歷右子樹 -> 根結(jié)點

/**
 * 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);
            // ③ 根結(jié)點
            result.push(root.val);
        }
    }
    postorder(root);
    return result;
};

根據(jù)兩種遍歷序列構(gòu)造樹

106.從中序與后序遍歷序列構(gòu)造二叉樹

/**
 * 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;
    }
    // 后序遍歷的最后一個節(jié)點一定是根節(jié)點
    let treeNode = new TreeNode(postorder[postorder.length - 1]);
    // 在中序遍歷中找到 根節(jié)點的位置
    let i = inorder.indexOf(postorder[postorder.length - 1]);
    // 根據(jù)左子樹的中序和后序遍歷構(gòu)建左子樹
    treeNode.left = buildTree(inorder.slice(0, i), postorder.slice(0, i));
    // 根據(jù)右子樹的中序和后序遍歷構(gòu)建右子樹
    treeNode.right = buildTree(inorder.slice(i + 1), postorder.slice(i, postorder.length - 1));
    return treeNode;
};

105. 從前序與中序遍歷序列構(gòu)造二叉樹

/**
 * 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;
    }
    // 前序遍歷的第一個節(jié)點一定是根節(jié)點
    let treeNode = new TreeNode(preorder[0]);
     // 在中序遍歷中找到 根節(jié)點的位置
    let i = inorder.indexOf(preorder[0]);
     // 根據(jù)左子樹的前序和中序遍歷構(gòu)建左子樹
    treeNode.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
     // 根據(jù)右子樹的前序和中序遍歷構(gòu)建右子樹
    treeNode.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
    return treeNode;
};

889. 根據(jù)前序和后序遍歷構(gòu)造二叉樹

const constructFromPrePost = (pre, post) => {
    const { length } = pre;
    if (length === 0) return null;
    // 前序遍歷的第一個節(jié)點一定是根節(jié)點
    const root = new TreeNode(pre[0]);
    // 在后序遍歷中找到 根節(jié)點的位置
    const index = post.indexOf(pre[1]);
     // 根據(jù)左子樹的前序和后序遍歷構(gòu)建左子樹
    root.left = constructFromPrePost(pre.slice(1, index + 2), post.slice(0, index + 1));
    // 根據(jù)右子樹的前序和后序遍歷構(gòu)建右子樹
    root.right = constructFromPrePost(pre.slice(index + 2, length), post.slice(index + 1, length - 1));
  
    return root;
  };

BFS

102.層序遍歷

按照高度順序惠毁，從上往下逐層遍歷節(jié)點犹芹。
先遍歷上層節(jié)點再遍歷下層節(jié)點。

/**
 * 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表示當(dāng)前層級
    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; 
};

最后

這次看完應(yīng)該理解了樹的兩種遍歷策略了吧仁讨，如果還不懂羽莺，建議再看一遍，或者自己去看leetcode相關(guān)的官方題解洞豁。

常考算法面試題系列：樹的遍歷

称馍＃考算法面試題系列：樹的遍歷