Swordoffer

题目 按之字形顺序打印二叉树 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 JS实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function Print(pRoot) { // write code here let result = []; if (pRoot === null) { return result; } let q = []; q.push(pRoot); …

题目 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 JS实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function isSymmetrical(pRoot) { // write code here return isSymmetricalTree(pRoot, pRoot); } function isSymmetricalTree(node1, node2) { //判断两个节点都是否为空 if …

题目 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 平衡二叉树一般指平衡树。 平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。 详解 /* * 链接：https://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222?f=discussion * 来源：牛客网 */ public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return getDepth(root) != -1; …

题目 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 JS实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function TreeDepth(pRoot) { // write code here if (pRoot == null) { return 0; } const left = TreeDepth(pRoot.left); const right = …

题目 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 JS实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function PrintFromTopToBottom(root) { // write code here let result = []; if (root === null) { return result; } let q = []; q.push(root); while (q.length != 0) { let len = q.length; …

题目 操作给定的二叉树，将其变换为源二叉树的镜像。 输入描述: 二叉树的镜像定义 //源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 //镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5 JS实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function Mirror(root) { // write code here if (root === null) { return; } if (root.left === null …

题目 我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？ 比如n=3时，2 * 3的矩形块有3种覆盖方法： ()[../images/offer10.png] 详解 每次使用两个变量a，b来计算下一个数的值sum，然后a，b，sum分别是斐波那契数列中的三个数，那么就令a=b，b=sum，这样a和b就往下移动了一个位置，再计算sum就是第4个数了，重复这个过程即可。 target = 1时，1种 target = 2时，2种 target = 3时，3种 target = 4时，5种 target = n …

题目 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 详解 关于本题，前提是n个台阶会有一次n阶的跳法。分析如下： f(1) = 1 f(2) = f(2-1) + f(2-2) //f(2-2)表示2阶一次跳2阶的次数。 f(3) = f(3-1) + f(3-2) + f(3-3) … f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n) 说明： 这里的f(n)代表的是n个台阶有一次1,2,…,n阶的跳法数。 n=1时，只 …

题目 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 详解 一次1阶或者2阶的跳法： a. 如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1); b. 假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2) c. 由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) d. 然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2 e. 可以发现最终得出的是一个斐波那契数列： | 1, (n=1) …

题目 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… , 这个数列从第3项开始，每一项都等于前两项之和。 JS实现 //递归实现 const Fibonacci = (n) => { if (n <= 0) { return 0; } if (n === 1) { return 1; } return Fibonacci(n - 1) + Fibonacci(n - 2); }; // …