Ahri-珊
昨天计划完成的时间太晚了没有来的及更新,今天准备在day2分享昨天做的LeetCode的题,然后在day3里分享一下这两天写的2048小游戏。
目录 (Table of Contents)
[TOCM]
[TOC]
LeetCode
111. Minimum Depth of Binary Tree
题目要求:
求二叉树的最小深度
心路历程
- 最小深度与最大深度的不同:最大深度需要遍历完整棵树,最小深度遍历完第一个叶子节点
- 如何实现遍历完第一个叶子节点停止:左右节点为空时结束递归
- 函数需要做什么:左右节点为空时返回1;左节点为空时往右找;右节点为空时往左找;左右节点都不为空时返回较小的深度+1
我的代码
var minDepth = function(root) {
if(!root)
return 0;
if(!root.left&&!root.right)
return 1;
if(!root.left)
return minDepth(root.right)+1;
if(!root.right)
return minDepth(root.left)+1;
return Math.min(minDepth(root.right),minDepth(root.left))+1;
};
112. Path Sum
题目要求:
给定一个二叉树和一个值sum,判断这棵树是否有这么一条从根节点到叶子节点的和为sum的路径。
如: 给定下面的二叉树并且sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1 你需要返回true, 因为存在这么一条路径 5->4->11->2 ,他们的和为 22.
心路历程
- 解读题意:Path的开始为根节点,结尾为叶子节点;Path中节点和为sum;找到符合前两个要求的返回ture,否则返回false
- 如何从根节点开始:中序遍历
- 如何到叶子节点结束:找到叶子节点就判断和是否为sum
- 如何找到所有的Path与当前Path和(current):中序遍历能够走完所有的路径,我们只需判断它是否往回走了,往回走了就将上个节点的值从current中减去。如:遍历到5->4->11->7后会再回到11遍历2,此时current需要-7;
- 如何实现4:a.从叶子节点往回走:遍历叶子节点时只判断current+root.val与sum是否相等,不增加current;b.非叶子节点往回走,遍历完它的子节点后current-=root.val;
我的代码
var current = 0;
var hasPathSum = function(root, sum) {
if(!root)
return false;
if(!root.left&&!root.right)
{
if(current+root.val==sum)
return true;
else
return false;
}
current = current +root.val;
var l = hasPathSum(root.left,sum);
var r = hasPathSum(root.right,sum);
current = current-root.val;
return l||r;
};
118. Pascal’s Triangle
题目要求:
输出杨辉三角前n层
心路历程
杨辉三角的规律:第一层为[1],第二层为[1,1],之后的每层开头与结尾均为1,并且下一层1与1 中间的树为上一层两两相加之和。
我的代码
var generate = function(numRows) {
var res = new Array();
if(numRows==0)
return res;
if(numRows==1)
return [[1]];
if(numRows==2)
return [[1],[1,1]];
res[0] = [1];
res[1] = [1,1];
for (var i = 2; i < numRows; i ++)
{
res[i] = new Array();
res[i].push(1);
for(var j = 0;j < i-1;j ++)
res[i].push(res[i-1][j]+res[i-1][j+1]);
res[i].push(1);
}
return res;
};
End
Comments