面试二叉树看这11个就够了

算法与数据结构 2019-11-27 3330

描述

不知道你有没有这种困惑，虽然刷了很多算法题，当我去面试的时候，面试官让你手写一个算法，可能你对此算法很熟悉，知道实现思路，但是总是不知道该在什么地方写，而且很多边界条件想不全面，一紧张，代码写的乱七八糟。如果遇到没有做过的算法题，思路也不知道从何寻找，那么这篇文章就主要为你解决这几个问题。

《剑指 offer》是准备数据结构与算法面试的一本好书，里边很多面试手写算法很多的注意的问题，但是基本都是用 C++ 实现的，书中每章节的分类都是按照性能和消耗以及手写代码的注意的几大点进行了分类，针对每个不同的点，进行数据结构与算法的混合实现。

二遍刷题，发现了还可以根据自身情况进行整理和分类。全部代码是用 JS 书写，都经过 Leetcode 标准测试（小部分Leetcode 没有的题目），对所有的算法题的特点进行总结分类，手写算法中，如何考虑到全部的边界条件；如果快速多种思路解决，如何将思路快速的转化为代码，这是这一篇重点分享的地方。

二叉树题目共有 11 题，我把这 11 题书中对实现方法和思路有详细的讲解，但是对于个人来说，以后遇到陌生的二叉树的题目怎么进行解决，通过对 11 个题的分析、整理，得出以下几个步骤，首先先来看这 11 个二叉树经典算法题。

PS：如果你已经做过这几道题，而且能够顺利的手写出来，不妨滑到最底部，希望最后的二叉树思路、测试用例以及代码编写的总结对你在面试中有所帮助（这篇文章精华所在）。

No.1

面试题7：重建二叉树

已知前序遍历为{1,2,4,7,3,5,6,8}，中序遍历为{4,7,2,1,5,3,8,6}，它的二叉树是怎么样的？

1、

思路

根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

空树、前序和中序不匹配 —— 输入测试。

3、

代码实现

1// 定义结点 2// class TreeNode{ 3// constructor(data){ 4// this.data = data; 5// this.left = null; 6// this.right = null; 7// } 8// } 9 10// 参数：前序遍历数组 ~ 中序遍历数组 11const reConstructBinaryTree = (pre, vin)=>{ 12 // 判断前序数组和中序数组是否为空 13 if(!pre || pre.length === 0 || !vin || vin.length === 0){ 14 return; 15 } 16 // 新建二叉树的根节点 17 var treeNode = { 18 val: pre[0] 19 } 20 // 查找中序遍历中的根节点 21 for(var i = 0; i < pre.length; i++) { 22 if (vin[i] === pre[0]) { 23 // 将左子树的前中序遍历分割开 24 treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i)); 25 // 将右子树的前中序遍历分割开 26 treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1)); 27 } 28 } 29 // 返回该根节点 30 return treeNode; 31} 32 33let pre = [1,2,4,7,3,5,6,8]; 34let vin = [4,7,2,1,5,3,8,6]; 35console.log(reConstructBinaryTree(pre,vin));

No.2

面试题8：二叉树的下一节点

给定一个二叉树的节点，如何找出中序遍历的下一节点。有两个指向左右子树的指针，还有一个指向父节点的指针。

1、

思路

求中序遍历的下一节点，就要分各种情况（明确中序遍历下一结点在二叉树中的位置有哪些），然后对某种情况详细分析。

下一结点可能存在的情况：

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

空树、前序和中序不匹配 —— 输入测试。

3、

代码实现

1 const getNextNode = (pNode)=>{ 2 // 判断该结点是否为 null 3 if(pNode == null){ 4 return; 5 } 6 7 // 当前结点有右子树且左子树 8 if(pNode.right !== null){ 9 pNode = pNode.right; 10 // 判断右子树是否有左子树 11 while(pNode.left !== null){ 12 pNode = pNode.left; 13 } 14 return pNode; 15 }else{ 16 // 判断当前结点是否存在父节点(如果为空,没有下一结点) 17 while(pNode.next !== null){ 18 if(pNode == pNode.next.left){ 19 return pNode.next; 20 }else{ 21 pNode = pNode.next; 22 } 23 } 24 // 没有下一结点 25 return null; 26 } 27 }

No.3

面试题26：树的子结构

输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。

1、

思路

通过判断两棵树的根节点否相同，如果相同，则递归判断树剩余的结点是否相同。如果不相同，则递归树的左右子节点进行对比找到相同的根节点。

2、

测试用例

是子结构、不是子结构 —— 普通测试。

只有左子节点、只有右子节点、只有一个结点 —— 特殊测试。

空树 —— 输入测试。

3、

代码实现

1 const TreeConstrutor = (nodeA, nodeB)=>{ 2 const result = false; 3 // 判断输入是否为 null 4 // nodeA 为 null 不会有子结构 5 if(nodeA == null){ 6 return false; 7 } 8 // 如果 nodeB 为 null,代表所有子结构比较完成 9 if(nodeB == null){ 10 return true; 11 } 12 13 // 如果根节点相同，则进行子结构全部的验证,返回验证的结果 14 if(nodeA.data === nodeB.data){ 15 result = match(nodeA, nodeB) 16 } 17 18 // 如果根节点不相同，继续递归遍历查找相同的根节点 19 return TreeConstrutor(nodeA.left, nodeB) || TreeConstrutor(nodeA.right, nodeB) 20} 21 22// 匹配根节点相同的子结构 23const match = (nodeA, nodeB)=>{ 24 if(nodeA == null){ 25 return false; 26 } 27 if(nodeB == null){ 28 return true; 29 } 30 // 判断匹配的当前结点是否相同 31 if(nodeA.data == nodeB.data){ 32 // 递归匹配其他子节点 33 return match(nodeA.left, nodeB.left) && match(nodeA.right, nodeB.right); 34 } 35 36 // 如果不相同 37 return false; 38}

No.4

面试题27：二叉树的镜像

请完成一个函数，如果一个二叉树，该函数输出它的镜像。

1、

思路

根节点的左右子节点相互交换，继续递归遍历，将子节点的左右结点进行交换，知道遇到叶子节点。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

空树 —— 输入测试。

3、

代码实现

1const insert = (root)=>{ 2 // 判断根节点是否为 null 3 if(root == null){ 4 return; 5 } 6 7 // 进行结点交换 8 Let tempNode = root.left; 9 root.left = root.right; 10 root.right = tempNode; 11 12 // 递归遍历剩余的子节点 13 insert(root.left); 14 insert(root.right); 15 16 // 返回根节点 17 return root; 18}

No.5

面试题28：对称二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

1、

思路

首先，观察一个对称的二叉树有什么特点？

结构上：在结构上实对称的，某一节点的左子节点和某一节点的右子节点对称。

规律上：我们如果进行前序遍历（根、左、右），然后对前序遍历进行改进（根、右、左），如果是对称的二叉树，他们的遍历结果是相同的。

考虑其他情况：

结点数量不对称

结点值不对称

2、

测试用例

对称二叉树、不对称二叉树（结点数量不对称、结点结构不对称）—— 普通测试。

所有结点值都相同的二叉树 —— 特殊测试。

空二叉树 —— 输入测试。

3、

代码实现

1var isSymmetric = (root)=>{ 2 // 判断二叉树是否为 null —— 输入测试， if(root == null){ 3 return true; 4 } 5 6 // 判断输入的二叉树,从根节点开始判断是否是对称二叉树 7 var Symmetric = (lNode, rNode)=>{ 8 // 判断左右结点是否都为 null 9 if(lNode == null && rNode == null){ 10 return true; 11 } 12 // 判断其中一个为 null 另一个不是 null 13 if(lNode == null && rNode !== null){ 14 return false; 15 } 16 if(lNode !== null && rNode == null){ 17 return false; 18 } 19 // 判断两个结点的值是否相同 20 if(lNode.val !== rNode.val){ 21 return false; 22 } 23 // 如果相同，继续递归判断其他的结点 24 return Symmetric(lNode.left,rNode.right) && Symmetric(lNode.right,rNode.left) 25 } 26 27 Symmetric(root.left,root.right) 28}

No.6

面试题32：从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。（按层遍历二叉树）

1、

思路

从根节点开始按层遍历打印结点（自左往右），下一层的遍历是上一层的字节点，但是我们发现想要获取到上层结点的子节点时，上层的父节点已经遍历过去可，想要在获取到，必须存储父节点。然后下层遍历的时候，自左往右取出父节点，依次打印子节点。

上方的解题思路中父节点的存储和遍历让我们想到一个熟悉的数据结构，对了，“先进先出”的思想，那就是队列。在遍历上一层结点的时候，先打印结点值，然后判断是够存在左右子树，如果存在，将给结点入队，直到该层的结点全部遍历完成。然后队列出队，分别打印结点，循环此步骤。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试

只有左、右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试

空树 —— 输入测试

3、

代码实现

1、参数：树的根节点。

2、判断是否为空。

3、打印结点值,判断该结点是否存在子节点，如果存在就入队。

4、出队，打印结点

5、循环上述步骤

1 var levelOrder = function(root) { 2 let result = []; // 存放遍历的结果 3 // 判断根节点是否为 null 4 if(root == null){ 5 return []; 6 } 7 // 声明一个队列 8 let queue = []; 9 queue.push(root) 10 11 // 出队，打印结结点、判断是否存在子节点 12 while(queue.length !== 0){ 13 let temp = []; // 存储每层的结点 14 let len = queue.length; 15 for(let j = 0;j < len;j++){ 16 // 出队 17 let tempNode = queue.shift(); 18 // 存储结点值 19 temp.push(tempNode.val) 20 // 判断出队的根节点是否有子节点 21 if(tempVal.left !== null){ 22 queue.push(tempVal.left) 23 } 24 if(tempVal.right !== null){ 25 queue.push(tempVal.left) 26 } 27 } 28 //存储每层的遍历的结点值 29 result.push(temp); 30 } 31 // 返回结果集 32 return result; 33 }

No.7

面试题33：二叉树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历。如果是返回 true，如果不是返回 false。假设输入的任意两个数字互不相同。

1、

思路

根据后续遍历的规律和二叉树具备的特点，可以找到的规律就是（左、右、根）序列的最后一个数为根节点，又根据二叉树的特点，左子节点小于根节点，右子节点大于根节点，分离出左右子节点，根据上边的规律，递归剩下的序列。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

空树 —— 输入测试。

3、

代码实现

1、参数：数组

2、判断数组是否为空

3、取数组的最后一个元素作为对比的根节点

4、根据根节点值的大小分割数组（分割数组的同时判断是否都满足小于根节点的要求）

5、判断分割数组是否是空

6、递归上方的步骤

1 const isPostorder = (arr)=>{ 2 // 判断数组是否为 null 3 if(arr.length == 0){ 4 return true; 5 } 6 7 // 取数组最后一个数字为根节点 8 let rootVal = arr[arr.length - 1]; 9 10 // 搜索小于根节点的值,并记录该结点的下标(除根节点外) 11 let i = 0; 12 for(;i < arr.length - 1;i++){ 13 if(arr[i] > rootVal){ 14 break 15 } 16 } 17 18 // 搜索大于根节点的值（除根节点外） 19 let j = 0; 20 for(;j < arr.length - 1; j++){ 21 if(rootVal > arr[j]){ 22 return false; 23 } 24 } 25 26 // 递归判断左子节点的值（先判断左子节点是够有值），默认返回 true 27 let left = true 28 if(i > 0){ 29 left = isPostorder(arr.slice(0, i)) 30 } 31 // 如果右子树不为空，判断右子树为二叉搜索树 32 let right = true 33 if(i < arr.length - 1){ 34 right = isPostorder(arr.slice(i,arr.length - 1)) 35 } 36 return (left && right) 37}

No.8

面试34：二叉树和为某一值路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输出整数的所有路径。从树的根节点开始往下一直到叶子节点所经过的节点形成一条路径。

1、

思路

1、找规律：需要遍历树的所有结点：我们会想到前、中、后遍历；需要存储遍历过的路径（节点值）：我们想到用数组存储

2、算法思想：前序遍历（根、左、右）的特点，从根到叶子节点，会从树自左向右依次遍历二叉树，所有可能的路径都会遍历到，所以使用前序遍历更佳。

每遍历一个结点就将其累加，然后判断累加的值是否等于目标值且子节点为叶子节点。如果是，则打印输出该路径；如果不是，则回退到上一父节点，此时数组中的数据结点进行删除，然后不断的遍历下一子节点，递归。

3、综上所述，存储结点路径的时候，涉及到累加结点和删除节点，我们可以将其抽象成入栈和出栈。然后遍历二叉树的所有路径可以用到递归的过程，让出栈和入栈与递归的状态达成一致，这到题就不难了。

2、

测试用例

完全二叉树、非完全二叉树（有一条路径满足、有多条路径满足、都不满足）—— 普通测试。

只有左子节点的二叉树、只有右子节点的二叉树、只有一个结点的二叉树 —— 特殊测试。

空二叉树、输入负数 —— 输入测试。

3、

代码实现

1 const treeSum = (root, targetSum)=>{ 2 // 判断输入的二叉树和整数 3 if(root == null || targetSum < 0){ 4 return false; 5 } 6 7 // 开始进行递归遍历二叉树进行查找满足条件的路径 8 let result = []; // 存放最后满足条件的路径 9 let pathStack = []; // 储存当前路径的栈 10 let currentSum = 0; // 当前累加的结果值 11 12 // 进行路径查找 13 FindPath(root, targetSum, currentSum, pathStack, result); 14 15 // 返回结果 16 return result; 17 } 18 19 const FindPath = (root, targetSum, currentSum, pathStack, result)=>{ 20 // 将当前跟根节点进行累加 21 currentSum = currentSum + root.val; 22 23 // 存储栈中 24 pathStack.push(root.val); 25 26 // 判断目标值是否相等且是否为叶子节点 27 if(currentSum == targetSum && root.left == null && root.right == null){ 28 // 打印路径 29 result.push(pathStack.slice(0)) 30 } 31 32 // 如果左子节点不为空 33 if(root.left !== null){ 34 FindPath(root.left, targetSum, currentSum, pathStack, result); 35 } 36 37 // 如果当前结点还有右子树，继续遍历 38 if(root.right !== null){ 39 FindPath(root.right, targetSum, currentSum, pathStack, result); 40 } 41 42 // 该路径遍历到叶子节点，还没有满足条件，则退回到父节点，进行下一结点的累加判断 43 pathStack.pop(); 44 }

No.9

面试题37：序列化二叉树

请实现两个函数，分别用来序列化二叉树和反序列化二叉树。

1、

思路

1、序列化：遍历二叉树，遇到叶子节点，将其转化为 $ 表示。

2、反序列化：根据前序遍历的特点（根、左、右），进行二叉树的还原。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

空树 —— 输入测试。

3、

代码实现

1 let result = []; 2var serialize = function(root) { 3 // 判空 4 if(root == null){ 5 result.push('$'); 6 return; 7 } 8 // 前序遍历 9 result.push(root.val) 10 serialize(root.left) 11 serialize(root.right) 12 // 打印 13 console.log(result) 14}; 15 16serialize(symmetricalTree);

No.10

面试题54：二叉树的第 K 大节点

给定一棵二叉搜索树，请找出其中的第 K 大节点。

1、

思路

要想找到第 K 大结点必要要知道排序，二叉树的前、中、后遍历中的中序遍历就是从小到大排序。然后遍历的同时计数找到第 K 大节点。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试。

K 的范围、空树 —— 输入测试。

3、

代码实现

1// 求二叉树中第 K 大节点 2var kthTallest = function(root, k) { 3 let res = [] 4 // 遍历 5 const inorder = (root) => { 6 if (root) { 7 inorder(root.left); 8 res.push(root.val); 9 inorder(root.right); 10 } 11 } 12 // 调用 13 inorder(root); 14 return res[res.length - k] 15};

No.11

面试题55：二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点（包含根、叶子节点）形成树的一条路径，最长路径的长度树的深度。

1、

思路

思路一：按层遍历，对按层遍历的算法进行改进，每遍历一次层进行加一。

思路二：寻找最长路径，借助遍历最长路径的设计思路记性改进。只需记录两个子树最深的结点为主。

2、

测试用例

完全二叉树、非完全二叉树 —— 普通测试。

只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

空树、前序和中序不匹配 —— 输入测试。

3、

代码实现

1var maxDepth = function(root) { 2 // 如果根节点为 null 3 if(root === null) return 0; 4 5 // 递归左子树 6 let depthLeft = maxDepth(root.left); 7 8 // 递归右子树 9 let depthRight = maxDepth(root.right); 10 11 // 将子问题合并求总问题 12 return Math.max(depthLeft,depthRight) + 1; 13};

总结归纳

通过《剑指 offer》以上十一个题，不是做过之后就记住了这么简单，而是通过以上二叉树题型的总结归纳，能不能举一反三，总结出二叉树面试题的解题思路，以后遇到二叉树相面试题能不能通过上边总结出来的步骤进行思考独立解决，这是这篇文章的重点。下面就分别通过解题思路、测试用例以及编写代码进行深入总结。

解题思路总结

1、根据树前（根左右）、中（左根右）、后（左右根）序遍历的规律来解决问题。

通过二叉树的遍历来找到规律，从而找到解题思路。

重建二叉树

根据前、中序遍历，找到二叉树的根节点和左右子树的规律，然后递归构建二叉树。

二叉树的下一节点

根据中序遍历，找出包含任何节点的一下节点的所有可能情况，然后根据情况分别进行判断。

二叉树的后续遍历序列

通过中序遍历找到打印二叉树结点的规律，可以判断此后续遍历是否为二叉树。

二叉树和为某一值的路径

选择二叉树的遍历，对每个节点进行存储判断，然后根据二叉树叶子节点的特点，进行对问题的解决。

二叉树的第 K 大结点

中序遍历的结果是从小到大，然后倒数找到第 K 大数据。

序列化二叉树

遍历二叉树，遇到 null 转化为特殊符号。

2、根据树的结构寻找规律来解决问题

通过二叉树的特点：左子节点小于父节点、右子节点大于父节点、树的节点可以进行递归等，以上特点又是更好的帮我们解决思路。

树的子结构

根据子结构和主体树的特点，对其树的结构进行分析，可以找到解题的思路。

镜像二叉树

观察镜像二叉树的左右子节点交换特点，可以找到解题思路。

对称二叉树

观察对称二叉树有什么特点，在结构上和遍历上寻找特点和规律，可以找到解题思路。

按层遍历二叉树

根据二叉树每层节点的结构关系（父子关系），可以进行每层遍历，通过上层找到下层的遍历结点。

反序列化二叉树

根据遍历的规律和二叉树的规律，将遍历结果生成一棵二叉树。

测试用例总结

通过以上题目中，我将测试用例分为三大种，测试代码的时候，在这三大种进行想就可以了。

※ 普通测试

※特殊测试

※输入测试

普通测试

普通测试从两个方面去想，第一个方面就是问题的本身，比如对称二叉树的判断，普通测试就是分别输入一个对称二叉树和非对称二叉树进行测试。第二个方面就是问题本身没有什么可以找到的测试，比如按层遍历二叉树，它的普通测试就是分别输入完全二叉树（普通二叉树也可以），非完全二叉树进行测试。

特殊测试

特殊测试强调的是树的特殊性，特殊的二叉树就那么几个，比如：只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树、没有结点的二叉树。

输入测试

输入测试，顾名思义，要对用户输入的参数进行判断，比如，你输入一棵树，要判断是否为空。再比如，求最大 K 结点，对 K 的取值范围进行判断。

代码编写

将二叉树的解题思路转化为代码除了熟练最基本的二叉树的增、删、改、查之外，最重要的就是二叉树的递归，因为二叉树的结构决定了用递归解决二叉树问题更加简便。但是递归的书写并不仅简单，因为它有递和归的过程，大脑并不能更好的去处理这些，可以去看之前总结递归的文章《数据结构与算法之递归系列》。

书写二叉树递归问题有一点特别重要，不要尝试的去想那个递归的过程，而是先去寻找到递归的终止条件，然后对每次递归的结果进行判断，然后让他递归去吧，再次强调千万别去思考过程。

学习编程不是做了多少题，而是能不能在做过的题和项目中总结经验，这是快速成长的必要条件。非常感谢各位的大力支持，下一篇我们再见。

打开APP阅读更多精彩内容