Ahri-珊

day22将分享LeetCode算法题257，258，263。

LeetCode

今天的三道题涉及到二叉树、质因子。

257. Binary Tree Paths

输出二叉树的所有路径

心路历程

1.定义一个全局变量path存放路径

2.每次调用binaryTreePaths清空之前path的数据

3.将当前节点与它的路径s作为patht的参数

4.遍历root，把每个子节点的值存入对应的s

5.遍历到根节点时，一条路径存完了，放入path数组

代码：

var path = [];
var binaryTreePaths = function(root) {
    path = [];
    if(!root)
        return path;
    var s = root.val+'';
    patht(root,s);
    return path;
};

var patht = function(root,s)
{
    if(root.left&&root.right)
        return patht(root.left,s+'->'+root.left.val)+patht(root.right,s+'->'+root.right.val);
    if(root.left)
        return patht(root.left,s+'->'+root.left.val);
    if(root.right)
        return patht(root.right,s+'->'+root.right.val);
    if(!root.left&&!root.right)
        path.push(s);
    return ;
}

258. Add Digits

感觉一句话概括不清楚，直接贴题目好了= =

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up: Could you do it without any loop/recursion in O(1) runtime?

心路历程

1.使用字符串来判断num的长度，一位则返回

2.长度大于1，遍历字符串，将字符串每一位转换为数字并累加

3.将累加结果作为下一次递归的参数

代码：

var addDigits = function(num) {
    var s = num+'';
    if(s.length==1)
        return num;
    else
        {
            var next = 0;
            for(let i=0;i<s.length;i++)
                {
                    next += parseInt(s[i]);
                }
            return addDigits(next);
        }
};

263. Ugly Number

找出那个不是只爱（质因子只有）2，3，5的丑渣数！

心路历程

1.判断一个数质因子是否只有2，3，5，只需判断这个数除以他们能否得到1（能被2，3，5谁整除就除以谁，都不能被整除了结果又不是1就说明还含其他因子）

2.num能被2，3，5谁整除就把除以谁后的结果作为下一次递归的参数

3.num等于1，返回true

4.不能被2，3，5整除，返回false

5.特殊：不能作为被除数的0直接返回false

代码：

var isUgly = function(num) {
    if(num==0)
        return false;
    if(num==1)
        return true;
    if(num%2==0)
        return isUgly(Math.floor(num/2));
    if(num%3==0)
        return isUgly(Math.floor(num/3));
    if(num%5==0)
        return isUgly(Math.floor(num/5));
    return false;
};

END