2021年6月9日 – 第 2 页

96. 不同的二叉搜索树（JS实现）

1 题目
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3

2 思路
这道题是卡特兰数的序列，递推公式h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2)

3代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
const d = [1,1];

for (let i=2; i<=n; i++) {
d[i] = 0;
for (let j=0; j<=i-1; j++) {
d[i] += d[j] * d[i-1-j];
}
}

return d[n];
};

验证二叉搜索树（JS实现）

1 题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/
1 3
输出: true
示例 2:
输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

2 思路
二叉搜索树的中序遍历是一个有序数组，因此这道题我们可以对二叉树进行中序遍历，若当前值小于或等于前一个值，则不是二叉搜索树

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
let prev;
function travse(p) {
if (!p) return true;
let statusLeft = travse(p.left);
if (typeof prev !== ‘undefined’ && prev >= p.val) return false;
prev = p.val;
let statusRight = travse(p.right);
return statusLeft && statusRight;
}

return travse(root);
};

对称二叉树（JS实现）

1 题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
\
3 3

2 思路
这道题可以用递归来解决，若有两个节点p和q相等，那么就检查p节点的左孩子和q节点的右孩子、p节点的右孩子和q节点的左孩子是不是都相等，就这样递归下去

return d(root.left, root.right);

function d(p, q) {
if (!p && !q) return true;

if (p && q && p.val === q.val) {
return d(p.left, q.right) && d(p.right, q.left);
} else {
return false;
}
}

};

二叉树的层序遍历（JS实现）

1 题目
给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

2 思路
这道题的主要思路是用队列来进行层序遍历，由于需要区分每一层，因此额外使用一个数组来存储下一层的节点

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {

const result = [];
if (!root) return result;

return result;
};

从前序与中序遍历序列构造二叉树（JS实现）

1 题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7

2 思路
这道题的主要思路是使用递归的方法来构造整个树，首先前序遍历中，*个节点是根节点，我们就可以将中序遍历数组划分为两个子数组，分别对应根节点的左右子树。然后针对左子树，前序遍历的第二个节点即为左子树的根节点，我们又可以将左子树的中序遍历数组进一步划分为两个子数组，就这样每次取前序遍历的一个元素，将中序数组层层划分下去

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {

function d(preArr, inArr, begin, end) {
if (begin > end) return null;

let index = inArr.indexOf(preArr[0]); //找到当前子树的根节点
let node = new TreeNode(preArr[0]); //新建子树的根节点
preArr.shift();
node.left = d(preArr, inArr, begin, index – 1); //继续划分左子树
node.right = d(preArr, inArr, index + 1, end); //继续划分右子树

return node;
}

return d(preorder, inorder, 0, inorder.length – 1);

function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
};

IOS使用EasyAr实现非unity（unity)案例介绍

##前言
###使用EasyAr首先我们需要在 http://www.easyar.cn/ 注册自己的账号，在开发栏创建自己的应用，生成key和自定义Bundle ID ，当然若是在自己的工程添加识别功能的话，只需将 Bundle ID 设置成工程的Bundle Identifier即可。

%title插图%num
##① IOS端EasyAr使用(unity)

###因为我们想要通过unity来实现识别，那我们自然要先下载工具unity 和样例，打开样例(注意这里Open的是一个文件夹)
选择Upgrade

%title插图%num
根据步骤，输入我们事先准备好的key

%title插图%num
###File -> Build Settings ->IOS -> Build And Run

%title插图%num

####就生成了一个Xcole文件.
打开Xcode文件，我们需要修改Bundle Identifier为我们设置的Bundle ID.还有在Info.plist文件中添加相应的视频、相机、相册权限
可参考：http://blog.csdn.net/w582324909/article/details/53539158

%title插图%num
IOS端EasyAr使用(unity) 并不难，看看文档就解决了，只是酷炫的效果需要在uiniy中取操作,所以我们可以采用非unity的方式实现自定义视频播放
② IOS端EasyAr使用(非unity)
###需求：
####从相册中获取识别图(或拍照获取)，从相册中获取识别视频(或拍摄获取)，实现当工程进入识别状态的时候，可以通过识别到不同的照片来跳转到下个页面播放原先指定的识别视频
####步骤：首先我们需要先下载 EasyAR的iOS的原生（非Unity）sample样例，如果你在导入EasyAR创建自己的工程，你需要添加如下这些framework。

%title插图%num
####当然Bundle Identifier和info.plist的设置是一样的。
####这边我们以 holloarvideo 为例
通过字符串定义一个key，输入我们事先准备好的key赋值给它。然后在 ***OpenGlView *** 的初始化方法里面传给EasyAR

– (id)initWithFrame:(CGRect)frame
{
frame.size.width = frame.size.height = MAX(frame.size.width, frame.size.height);
self = [super initWithFrame:frame];
if(self){
[self setupGL];
EasyAR::initialize([key UTF8String]);
ar.initGL();
}

return self;
}

####这样，我们*基本的配置就完成了。
####扫描工程中原本的指定图片，我们可以看到相应的案例视频。那么这些图片和视频是通过扫描方式识别播放的呢？不难发现，在***OpenGlView *** 的函数 ***void HelloARVideo::render()***中

%title插图%num

通过判断识别的图片与指定图片是否一致，一致就创建播放器，通过open的三种方法，打开普通视频，透明视频和加载网络视频，再在这里，通过矩阵变换映射的方式展示视频效果。

####而根据需求，我们应该在识别前创建一个页面去做图片和视频的选择，然后当我们点击识别的时候播放我们指定的视频，在这里我的做法是通过从相册中选取照片(或拍照)，从相册中选取视频(或拍摄)，取得相应的照片和视频，将它们存放在沙盒中，然后在函数 void HelloARVideo::render() 中将固定的图片名和视频名替换掉，这样，就实现了从单一的图片视频播放，都任意可指定图片视频播放，但是，由于需求是识别到后跳转播放，所以我们不能用样例自带的矩阵投影变化的方法播放视频，而是在

if(frame.targets()[0].target().name() == 图片名 && texid[0]) {
// 在这里去实现播放
}

又因为我们的识别ViewControl并没有直接处理识别这个功能，而是在OpenGlView中去做识别，而VC(指ViewControl)是通过控制创建和销毁OpenGlView来实现识别，那么我们想要做页面间的跳转就只能在这个实现播放处去传值或者响应事件，又由于.mm文件的限制，我选择用通知，当识别到图片时，发送一个通知给VC。让页面 dismissViewControllerAnimated
然后重写VC的初始化方法，传一个Block给它，当VC dismiss时调用Block,Block跳转新页。
这样就实现了识别后跳转新页，再在新页实现播放等功能，完成需求。

从中序与后序遍历序列构造二叉树（JS实现）

1 题目
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7

2 思路
这道题的主要思路跟从中序和前序序列构造二叉树，只不过前序换成了后序，我们就需要先构造右子树，再构造左子树

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
function d(pArr, inArr, begin, end) {
if (begin > end) return null;

let nodeValuie = pArr.pop();
let index = inArr.indexOf(nodeValuie);
let node = new TreeNode(nodeValuie);

node.right = d(pArr, inArr, index + 1, end);
node.left = d(pArr, inArr, begin, index – 1);

return node;
}

return d(postorder, inorder, 0, inorder.length – 1);

function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
};

将有序数组转换为二叉搜索树（JS实现）

1 题目
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的*对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5

2 思路
这道题的主要思路是首先找到数组的中点，中点*为根节点，然后中点两侧的子数组就为左右子树，随后利用继续对左右两边进行划分，递归进行

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
function d(arr, low, high) {
if (low > high) return null;
let mid = Math.floor((low + high) / 2);
let node = new TreeNode(arr[mid]);

node.left = d(arr, low, mid – 1);
node.right = d(arr, mid+1, high);

return node;
}

if (nums.length === 0) return null;
return d(nums, 0, nums.length – 1);

function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
};

有序链表转换二叉搜索树（JS实现）

1 题目
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的*对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5

2 思路
这道题我是将链表转换为数组，然后再用递归的方法来划分数组构造二叉树的，题解有更巧妙的中序遍历递归构造数

3代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function(head) {

if (!head) return null;
const nums = [];

while(head) {
nums.push(head.val);
head = head.next;
}
return d(nums, 0, nums.length – 1);

function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

function d(arr, low, high) {
if (low > high) return null;
let mid = Math.floor((low + high) / 2);
let node = new TreeNode(arr[mid]);

node.left = d(arr, low, mid – 1);
node.right = d(arr, mid + 1, high);

return node;
}
};

平衡二叉树（JS实现）

1 题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的*对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。

2 思路
这道题主要思路从底向上遍历，每次节点深度加1，判断每个节点的左右子节点的深度差是否超过1

function d(root) {
if (!root) return 0;

let leftDepth = d(root.left);
let rightDepth = d(root.right);

if (!status) return -1;

if (Math.abs(leftDepth – rightDepth) > 1) {
status = false;
}

return Math.max(leftDepth, rightDepth) + 1;
}

d(root);

return status;
}

一	二	三	四	五	六	日
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30