leetcode-96-98-101-102-104

leetcode96题98题101题102题104题

leetcode96题(不同的二叉搜索树):

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

示例

解答(动态规划):

问题是计算不同二叉搜索树的个数。为此,我们可以定义两个函数:
G(n): 长度为n的序列的不同二叉搜索树个数。
F(i,n): 以i为根的不同二叉搜索树个数(1≤i≤n)。
可见:G(n)是要解决问题需要的函数。

二叉搜索树的总数 G(n)是对遍历所有i (1 <= i <= n) 的 F(i, n)之和。换而言之:
公式

特别的,对于边界情况,当序列长度为 1(只有根)或为 0 (空树)时,只有一种情况。亦即:G(0)=1, G(1)=1.

给定序列 1 ... n,我们选出数字 i 作为根,则对于根 i 的不同二叉搜索树数量 F(i,n),是左右子树个数的笛卡尔积

公式

最终:需要求解的公式变为:

公式

为了计算函数结果,我们从小到大计算,因为 G(n)的值依赖于 G(0) … G(n-1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var numTrees = function(n) {//用动态规划的方法
var G = [];
for(var i=0;i<=n;i++){//初始化G矩阵,G[i]表示以i作为结束节点的二叉搜索树个数
if(i==0||i==1){//当没有节点,或者只有一个节点的时候,二叉搜索树个数为1
G[i] = 1;
}else{
G[i] = 0;
}
}
for(var i=2;i<=n;i++){//以i作为结束节点时的情况
for(var j=1;j<=i;j++){//以j作为根节点的情况
G[i] = G[i] + G[j-1]*G[i-j];
}
}
return G[n];
};

leetcode98题(验证二叉搜索树):

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。

  • 节点的右子树只包含大于当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。
示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var isValidBST = function(root) {
return judgeBST(root,null,null)
};
function judgeBST(root,lower,higher){
if(root==null){
return true;
}
var val = root.val;
if(lower!=null&&lower>=val){//如果下界值比该值高,返回false
return false;
}
if(higher!=null&&higher<=val){//如果上界值比该值低,返回false
return false;
}
if(!judgeBST(root.left,lower,val)){//如果左子树不是BST,返回false
return false;
}
if(!judgeBST(root.right,val,higher)){//如果右子树不是BST,返回false
return false;
}
return true;
}

leetcode101(对称二叉树):

给定一个二叉树,检查它是否是镜像对称的。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
var isSymmetric = function(root) {
return isMirror(root,root);
};
function isMirror(root1,root2){
if(root1==null&&root2==null){
return true;
}
if(root1==null||root2==null){
return false;
}
return (root1.val==root2.val)&&isMirror(root1.left,root2.right)&&isMirror(root1.right,root2.left);
}

leetcode102(二叉树的层次遍历):

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var levelOrder = function(root) {
if(root==null){
return [];
}
var resultArr = [];
var queue = [];
queue.push(root);
while(queue.length!=0){
var length = queue.length;
var tempVal = [];
for(var i=0;i<length;i++){
var temp = queue.shift();
tempVal.push(temp.val);
if(temp.left!=null){
queue.push(temp.left);
}
if(temp.right!=null){
queue.push(temp.right);
}
}
resultArr.push(tempVal);
}
return resultArr;
};

leetcode104(二叉树的最大深度):

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:

示例

解答:
1
2
3
4
5
6
7
8
var maxDepth = function(root) {
if(root==null){
return 0;
}
var left_height = maxDepth(root.left);
var right_height = maxDepth(root.right);
return Math.max(left_height,right_height)+1;
};
分享到