lC - 104. 二叉树的最大深度

难度:简单

题目描述

难度简单877收藏分享切换为英文接收动态反馈

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

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

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

示例:
给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

MyCode

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        else if(root->left == nullptr && root->right == nullptr) return 1;
        else if(root->left != nullptr && root->right == nullptr) 
            return maxDepth(root->left) + 1;
        else if(root->left == nullptr && root->right != nullptr)
            return maxDepth(root->right) + 1;
        else return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

复杂度分析

  • 时间复杂度:O(n),遍历二叉树所有元素就行

  • 空间复杂度:O(hegiht),递归需要递归调用栈存储临时变量

TaCode

深度优先搜索

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

复杂度分析

  • 时间复杂度:O*(*n),其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
  • 空间复杂度:O*(*height),其中height 表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。

广度优先搜索

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
    }
};

复杂度分析

  • 时间复杂度:O*(*n),其中 n为二叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。
  • 空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到 O(n)O(n)。

总结

官方的题解更为简洁,是自己太菜了。还有第一次提交的时候竟然忘了处理root为nullptr的情况,淦。

LC - 62. 不同路径

难度:中等

题目描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

递归求解

本题使用动态规划更好一些,我在此给出递归的方法。
对象含义如下:

  • pair<int, int > {m,n}:当前坐标
  • map<pair<int, int>, int> map[{m,n}] : 表示起点到点{m,n}的路径数量。

递归思路如下:

  • 递归终止条件:当点在最上一条边或最左一条边时,仅有一条路径
  • 递归关系式:点{m,n}的路径个数 = 点{m - 1,n}的路径个数 + 点{m,n - 1}的路径个数
  • 本题必须使用map存储数据,否则重复计算会造成超时。

Code

class Solution {
private:
    int func(map<pair<int, int>, int> &map, int m, int n){
        // 如果map没有{m,n}
        if(map.find({m , n}) == map.end()){
            // 递归终止条件 当点在最上一条边或最左一条边时,仅有一条路径
            if(n == 1 || m == 1)    map[{m , n}] = 1;
            // 递归关系式   点{m,n}的路径 = 点{m - 1,n}的路径 + 点{m,n - 1}的路径
            else    map[{m, n}] = func(map, m - 1, n) + func(map, m, n - 1);
        }
        // 如果有,那么直接返回
        return map[{m , n}];
    }
public:
    int uniquePaths(int m, int n) {
        if(m <= 0 || n <= 0) return 0;
        map<pair<int, int>, int> map;
        return func(map, m, n);
    }
};

总结

使用递归后注意优化,可以使用map或数组存储数据,类似于回溯中的剪枝。

剑指 - 16 数值的整数次方

难度中等

题目描述

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即, x n x^n xn)。不得使用库函数,同时不需要考虑大数问题。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:

输入:x = 2.10000, n = 3
输出:9.26100

示例 3:

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

提示:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

Code

class Solution {
private:
    map<int, double> m;
    double pow(double x, unsigned int n){
        if(m.find(n) == m.end()){
            if(n == 0){
                m[0] = 1;
            }
            else if(n == 1){
                m[1] = x;
            }
            else{
                m[n] = pow(x, n /2) * pow(x, n - n /2);
            }
        }
        return m[n];
    }
public:
    double myPow(double x, int n) {
        if(n == 0) return 1;
        else if(n > 0) {
            return pow(x, n);
        }else{
            long int n_ = n;
            unsigned int n__ = -n_;
            // return 1/pow(x, -n);
            return 1/pow(x, n__);
        }
    }
};

总结

注意第26行,若使用这段代码,对于测试用例 x = 1.00000,n = -2147483648,报错如下。

Line 26: Char 29: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:36:29

n为int类型,四个字节,范围是 [ − 2 15 , 2 15 − 1 ] [-2^{15},2^{15} - 1] [215,2151]即为 [ − 2147483648 , 2147483647 ] [-2147483648,2147483647] [2147483648,2147483647]

error: negation of -2147483648 cannot be represented in type ‘int’; cast to an unsigned type to negate this value to itself (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:36:29


n为int类型,四个字节,范围是$[-2^{15},2^{15} - 1]$即为$[-2147483648,2147483647]$。

n = -2147483648取反超出了int的范围,所以本题中将 n 转换为unsigned int类型。