重建二叉树
1. 题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。
2. 解题思路
前序遍历的第一个元素一定是树的根结点
在中序遍历中找到此节点,左边是左子树,右边是右子树
根据左右子树的长度,再次划分两个序列,进一步递归
3. 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647/** * 二叉树结点类 */class Node { constructor(value, left = null, right = null) { this.value = value this.left = left this.right = right }}/** * 根据前序遍历和中序遍历重构二叉树 * @param {Array} preorder * @param {Array} inorder * @return {Nod ...
判断是否子树
1. 题目描述输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。
树的节点定义如下:
12345678910/** * 二叉树结点类 */class Node { constructor(value, left = null, right = null) { this.value = value this.left = left this.right = right }}
2. 思路分析假设判断的是p2是不是p1的子树,实现分为 2 个部分:
遍历树的函数hasSubTree:遍历 p1 的每个节点,如果当前节点的 value 和 p2 根节点的 value 相同,立即进入判断函数(下一个函数);否则继续遍历
判断子树的函数doesTree1HaveTree2:比较当前节点的值,再递归比较 p1 和 p2 的左右节点的值
3. 代码实现123456789101112131415161718192021222324252627282930313233343536373839404 ...
二叉树的镜像
1. 题目描述请完成一个函数,输入一个二叉树,该函数输出它的镜像
2. 解题思路书上给了一个示意图:
显而易见,从根节点开始,交换左右子树的位置;再照这个思路向下处理子树节点。
3. 代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * 二叉树结点类 */class Node { constructor(value, left = null, right = null) { this.value = value this.left = left this.right = right }}/** * 二叉树镜像函数 * @param {Node} root */function mirrorBinaryTree(root) { if (root === null) { return } // ...
二叉搜索树的后序遍历序列
1. 题目描述输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
2. 思路描述因为是后序遍历,所以根节点是最后一个元素。然后前面序列分为 2 部分,有一部分是左子树,有一部分是右子树。
根据二叉搜索树的性质,左子树的元素一定小于最后一个元素,右子树的元素一定大于最后一个元素。
根据这个思路,一直递归下去即可。只要所有部分都满足二叉搜索树的性质,那么符合条件。
3. 代码实现123456789101112131415161718192021222324252627282930313233343536373839/** * 判断是否是二叉搜索树的后序遍历结果 * @param {Array} tailOrder 后序遍历顺序 */function isBST(tailOrder) { // 空序列代表空树, 这里认为是BST if (tailOrder.length === 0) { return true } ...
二叉树中和为某一值的路径
1. 题目描述输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
2. 思路分析
每次来到新的节点,记录新节点信息
检查新节点是否是叶子节点,如果是,判断路径上的节点值总和是否符合条件;如果不是,继续递归处理左右子树,回到第 1 步
最后需要将新节点的信息移除
3. 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061/** * 二叉树结点类 */class Node { constructor(value = 0, left = null, right = null) { this.value = value this.left = left this.right = right }}/** * * @param {Nod ...
二叉树层序遍历
1. 题目描述从上往下打印出二叉树的每个结点,同一层的结点按照从左到右的顺序打印。
2. 思路分析借助队列这种“先入先出”的线性数据结构即可。每次访问队列中的元素的时候,输出它的值,并且将其非空左右节点放入队列中。直到队列为空,停止输出,结束函数循环即可。
3. 代码实现1234567891011121314151617181920212223242526272829303132333435class TreeNode { constructor(value, left = null, right = null) { this.value = value this.left = left this.right = right }}/** * 层级遍历二叉树 * @param {TreeNode} root */function levelTravel(root) { const queue = [root] while (queue.length) & ...
二叉树转双向链表
1. 题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
2. 思路分析在搜索二叉树中,左子结点的值总是小于父结点的值,右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子结点的指针调整为链表中指向后一个结点指针。
因为要遍历树,所以要选取遍历算法。为了保证遍历的有序性,采用中序遍历。在 convertNode 函数实现中,注意 lastNodeInList 语意,剩下的按照思路写出来即可。
3. 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364class TreeNode { constructor(value, left = null, right = null) { this.value = va ...
判断是否是平衡二叉树
1. 题目描述判断一棵树是不是平衡二叉树。
2. 思路分析思路一:计算出左右子树的深度,然后检查差。递归继续判断左子树和右子树是不是平衡二叉树。
思路二:先计算左子树和右子树是不是平衡二叉树,然后再计算本身是不是平衡二叉树。
关于思路二为什么能比思路一更好,请看代码。
3. 代码实现3.1 树的深度先递归实现树的深度函数:
12345678910111213141516171819202122232425262728class Node { /** * * @param {Number} value * @param {Node} left * @param {Node} right */ constructor(value, left, right) { this.value = value this.left = left this.right = right }}/** * 获取二叉 ...
二进制中1的个数
1. 题目请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如把 9 表示成二进制是 1001,有 2 位是 1。因此如果输入 9,该函数输出 2。
2. 思路注意到,如果要判断一个二进制数指定位数是否为 1,比如这个二进制数是 1011。那么只需要构造除了这个位为 1,其他位为 0 的二进制即可,这个例子是 0100。
两者进行&运算,如果结果为 0,那么指定位数不为 1;否则为 1。
现在事情就简单了,只要准备数字1,每次与原数进行&操作,然后左移1;重复前面的步骤,就能逐步比较出每一位是不是1。
3. 代码实现1234567891011121314151617181920212223/** * @param {Number} n */function numberOf1(n) { let count = 0, flag = 1 while (flag) { if (flag & n) { ++count } ...
二进制中1的个数进阶版
1. 优化做法有个不错的规律,对于一个整数n,运算结果n & (n - 1)可以消除而今中从右向左出现的第一个1。比如二进制数011,减去 1 是010,做与运算的结果就是010。
利用这个性质,可以逐步剔除原数二进制中的1。每次剔除,统计量count都加 1;直到所有的1都被移除,原数变成0。
12345678910111213141516171819/** * @param {Number} n */function numberOf1(n) { let count = 0 while (n) { ++count n = n & (n - 1) } return count}/** * 测试代码 */console.log(numberOf1(3))
2. 如何判断 2 的整次方如果一个数是 2 的整次方,那么只有一个二进制位为 1。所以,n & (n - 1)如果不是 1,说明二进制表示中有多个 1,那么就不是 2 的整次方;否则,就是得。
1 ...