lc-day9

发表于

559. N 叉树的最大深度

题目

今天的lc每日一题

题目很简单，但是我猛然间将现在的代码和以前的代码做了一个对比，有了新发现

下面是我今天的代码，我的代码思路是每递归深入一层，就更新一次深度（初始深度为1），最后的全局变量就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxH;
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        dfs(root, 1);
        return maxH;
    }

    void dfs(Node* root, int h){
        if(root == nullptr) return;
        if(maxH < h) maxH = h;
        for(int i = 0; i < root->children.size(); i++){
            dfs(root->children[i], h + 1);
        }        
    } 
};

这是我以前的代码，后序遍历，这就不是在求深度了，这是从底层往高层算，是在回溯，求的是高度，而二叉树的高度值与深度值大小相同，所以代码也就过了。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        int max1 = 0;
        for(int i = 0; i < root->children.size(); i++) 
        max1 = max(max1, maxDepth(root->children[i]));
        return max1 + 1;
    }
};

这再次印证了Carl的话，递归和回溯的区别，一个去一个回，是截然不同的