常考算法面试题系列：树的遍历
首文发布在 个人博客
两种通用的遍历树的策略
DFS(深度优先遍历)：先序遍历，中序遍历，后序遍历；
BFS(广度优先遍历)：层序遍历
深度优先遍历（DFS）
这种方法以深度 depth 优先为策略，从根节点开始一直遍历到某个叶子节点，然后回到根节点，在遍历另外一个分支。
根据根节点，左孩子节点和右孩子节点的访问顺序又可以将 DFS 细分为先序遍历 preorder，中序遍历 inorder 和后序遍历 postorder。
广度优先遍历（BFS）
按照高度顺序，从上往下逐层遍历节点。
先遍历上层节点再遍历下层节点。
下图中按照不同的方法遍历对应子树，得到的遍历顺序都是 1-2-3-4-5。根据不同子树结构比较不同遍历方法的特点。
图片来源leetcode题解
相关题目（leetcode）
DFS
先序遍历、中序遍历、后序遍历
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;
};
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;
};
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;
};
根据两种遍历序列构造树
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;
};
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;
};
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
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相关的官方题解。
发表评论 (审核通过后显示评论)：