重建二叉树
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 ...
