前言
二叉树相关的面试题也是前端面试中非常重要的一部分。那二叉树是什么样的一种结构呢？
二叉树是一种每个Node节点都不超过两个子树的树结构。一个完整的二叉树，每个节点都是由根节点、左节点、右节点组成。
// 定义节点类型 interface TreeNode { // 当前节点的值 value: number; // left节点有可能也是个树，也有可能直接是null left: TreeNode | null; // right节点有可能也是个树，也有可能直接是null right: TreeNode | null; } // 定义一个二叉树 const binaryTree: TreeNode = { value: 5, left: { value: 3, left: { value: 2, left: null, right: null }, right: { value: 4, left: null, right: null } }, right: { value: 7, left: { value: 6, left: null, right: null }, right: { value: 8, left: null, right: null } } }
在二叉树中，如果想遍历所有二叉树的节点，有三种不同的顺序：前序遍历、中序遍历、后序遍历
前序遍历
首先我们要明白什么是前序遍历，是指展示节点的顺序依次为：root -> left -> right。注意，一定要遵守这个规则。
我们从代码上来看一下。
/** * @method preOrderTraversal * @description 二叉树的前序遍历 * @param tree TreeNode | null 二叉树 * @returns void */ function preOrderTraversal(tree: TreeNode | null) { // 1. 首先输出root节点即根节点 // 需要注意的时，tree有可能是null，临界条件判断，或者可以说是递归终止的条件 if (!tree) return; // 输出根节点的值 console.log(tree.value); // 2. 输出left节点 preOrderTraversal(tree.left); // 3. 输出right节点 preOrderTraversal(tree.right); }
调用函数，看下输出的结果：
// 5、3、2、4、7、6、8 => root -> left -> right preOrderTraversal(binaryTree);
中序遍历
中序遍历的规则是：left -> root -> right
继续上代码：
/** * @method preOrderTraversal * @description 二叉树的前序遍历 * @param tree TreeNode | null 二叉树 * @returns void */ function middleOrderTraversal(tree: TreeNode | null) { // 临界点判断 if (!tree) return; // 1. 先输出left的值 middleOrderTraversal(tree.left); // 2. 输出root根节点的值 console.log(tree.value); // 3. 输出right的值 middleOrderTraversal(tree.right); }
调用函数，看下输出的结果：
// 2、3、4、5、6、7、8 => left -> root -> right middleOrderTraversal(binaryTree);
后序遍历
后序遍历的原则是：left -> right -> root
/** * @method postOrderTraversal * @description 二叉树的后序遍历 * @param tree * @returns */ function postOrderTraversal(tree: TreeNode | null) { // 临界点判断 if (!tree) return; // 1. 先输出left的值 postOrderTraversal(tree.left); // 2. 输出right的值 postOrderTraversal(tree.right); // 3. 输出根节点的值 console.log(tree.value); }
调用函数，看下输出的结果：
// 2、4、3、6、8、7、5 => left -> root -> right postOrderTraversal(binaryTree);
二叉树的遍历非常简单，主要考察的是对前序遍历、中序遍历、后序遍历概念的理解。
