tree 先序周遊 葉子結點_常考算法面試題系列：樹的周遊

首文釋出在 個人部落格

兩種通用的周遊樹的政策

DFS(深度優先周遊)：先序周遊，中序周遊，後序周遊；

BFS(廣度優先周遊)：層序周遊

深度優先周遊(DFS)

這種方法以深度 depth 優先為政策，從根節點開始一直周遊到某個葉子節點，然後回到根節點，在周遊另外一個分支。

根據根節點，左孩子節點和右孩子節點的通路順序又可以将 DFS 細分為先序周遊 preorder，中序周遊 inorder 和後序周遊 postorder。

廣度優先周遊(BFS)

按照高度順序，從上往下逐層周遊節點。

先周遊上層節點再周遊下層節點。

下圖中按照不同的方法周遊對應子樹，得到的周遊順序都是 1-2-3-4-5。根據不同子樹結構比較不同周遊方法的特點。

相關題目(leetcode)

DFS

先序周遊、中序周遊、後序周遊

先序周遊為：根節點 -> 前序周遊左子樹 -> 前序周遊右子樹

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;

};

中序周遊為：中序周遊左子樹 -> 根結點 -> 中序周遊右子樹

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;

};

後序周遊為：後序周遊左子樹 -> 後序周遊右子樹 -> 根結點

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;

};

根據兩種周遊序列構造樹

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;

};

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;

};

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

按照高度順序，從上往下逐層周遊節點。

先周遊上層節點再周遊下層節點。

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相關的官方題解。