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相关的官方题解。