leetcode 9.07-9.13

2020-09-12

50 Pow(x, n)
637 二叉树的层平均值

50. Pow(x,n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：二分法，递归

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if x == 0:
            return 0
        if n == 0:
            return 1
        
        def Pow(_x, _n):
            if _n == 1:
                return _x
            ret = Pow(_x, _n/2)
            if _n % 2 == 0:
                return ret * ret
            else:
                return _x * ret * ret

        if n > 0:
            return Pow(x, n)
        else:
            return 1 / Pow(x, -n)

637. Pow(x,n)

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1：

输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

提示：

节点值的范围在32位有符号整数范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：层序遍历，一层一个循环，记下层数。比较简单

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        std::queue<TreeNode*> q;
        vector<double> ret;
        if (root == NULL) return ret;
        q.push(root);
        while(!q.empty()) {
            int len = q.size();
            long long int sum = 0;
            for(int i = 0; i < len; i++) {
                auto p = q.front();
                q.pop();
                if(p->left)  q.push(p->left);
                if(p->right) q.push(p->right);
                sum += p->val;
            }
            ret.push_back((double)sum/len);
        }
        return ret;
    }
};