Ahri-珊

昨天计划完成的时间太晚了没有来的及更新，今天准备在day2分享昨天做的LeetCode的题，然后在day3里分享一下这两天写的2048小游戏。

目录 (Table of Contents)

[TOCM]

[TOC]

LeetCode

111. Minimum Depth of Binary Tree

题目要求：

求二叉树的最小深度

心路历程

  1. 最小深度与最大深度的不同：最大深度需要遍历完整棵树，最小深度遍历完第一个叶子节点
  2. 如何实现遍历完第一个叶子节点停止：左右节点为空时结束递归
  3. 函数需要做什么：左右节点为空时返回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.

心路历程

  1. 解读题意：Path的开始为根节点，结尾为叶子节点;Path中节点和为sum;找到符合前两个要求的返回ture，否则返回false
  2. 如何从根节点开始：中序遍历
  3. 如何到叶子节点结束：找到叶子节点就判断和是否为sum
  4. 如何找到所有的Path与当前Path和（current）：中序遍历能够走完所有的路径，我们只需判断它是否往回走了，往回走了就将上个节点的值从current中减去。如：遍历到5->4->11->7后会再回到11遍历2，此时current需要-7；
  5. 如何实现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