深度优先搜索和宽度优先搜索

引言

主要是做这一道题的时候, 虽然也做出来了, 但是还是不太熟练, 而且也不是最优.

宽度优先 (BFS)

第一个是我写, 思路没有问题, 就是说用数组记录每层的节点数感觉没有必要.

int maxLevelSum(TreeNode *root) {

    if (root == nullptr) {  // 如果树为空的话直接返回 0
        return 0;
    }

    queue<TreeNode *> q;

    q.push(root);

    vector<int> level = {1, 0};
    int curr_level = 0;

    int sum = root->val;    // 给第一层赋值
    int sum_level = 0;

    int loop_sum = 0;       // 循环中进行求和的临时变量

    while (! q.empty()) {

        level[curr_level] -= 1; // 每次弹出都从这里减去一个元素数量
        TreeNode *node = q.front();
        q.pop();

        loop_sum += node->val;  // 求和

        if (node->left) {       // 左子节点入栈
            q.push(node->left);
            level[curr_level + 1]++;
        }

        if (node->right) {      // 右子节点入栈
            q.push(node->right);
            level[curr_level + 1]++;
        }

        if (level[curr_level] == 0) {   // 到了换层的时候了

            if (loop_sum > sum) {
                sum = loop_sum;
                sum_level = curr_level;
            }

            curr_level++;
            level.push_back(0);
            loop_sum = 0;   // 这里忘记了要清零了, 之前把这个放在了上一个 if 中 555
        }
    }

    return sum_level + 1;   // 题目中的层是从 1 开始的
}

第二个是别人写的, 感觉比较简洁


int maxLevelSumBetter(TreeNode *root) {
    queue<TreeNode *> q;            // 用于广度优先搜索的队列
    q.push(root);                   // 将根节点 (第一层先入列)
    int ans = INT_MIN;              // 没有用 root->val 作为初始层的和
    int i = 0;                      // 第 0 层的结果是 INT_MIN
    int h = 1;                      // h = 1 表示第一层
    while (! q.empty()) {
        int n = q.size();           // n 实际上就是即将遍历的这一层的节点数
        int t = 0;                  // t 是计算这里层和的临时变量
        while (n--) {
            TreeNode *x = q.front();
            q.pop();
            t += x->val;
            if (x->left) q.push(x->left);
            if (x->right) q.push(x->right);
        }
        if (t > ans) {
            ans = t;
            i = h;
        }
        h++;
    }
    return i;
}

深度优先 (DFS)

没想到遍历每层还可以用深度优先的方式:

class Solution {
    vector<int> sum;

    void dfs(TreeNode *node, int level) {
        if (level == sum.size()) {
            sum.push_back(node->val);
        } else {
            sum[level] += node->val;
        }
        if (node->left) {
            dfs(node->left, level + 1);
        }
        if (node->right) {
            dfs(node->right, level + 1);
        }
    }

public:
    int maxLevelSum(TreeNode *root) {
        dfs(root, 0);
        int ans = 0;
        for (int i = 0; i < sum.size(); ++i) {
            if (sum[i] > sum[ans]) {
                ans = i;
            }
        }
        return ans + 1; // 层号从 1 开始
    }
};

2022 年 8 月 21 日

今天又用 bfs 写了一遍

class Solution {
public:
    int maxDepth(TreeNode* root) {

        if (root == nullptr) return 0;

        int size = 0;
        std::queue<TreeNode*> q;

        q.push(root); ++size;

        int level = 0;
        while (! q.empty()) {

            TreeNode* head = q.front();
            --size;

            if (size == 0) {
                ++level;
                size = q.size();
            }

            if (head->left) q.push(head->left);
            if (head->right) q.push(head->right);
            q.pop();
        }

        return level;
    }
};

class Solution1 {
public:
    int maxDepth(TreeNode* root) {

        if (root == nullptr) return 0;

        int size = 0;
        std::queue<TreeNode*> q;

        q.push(root); ++size;

        int level = 0;
        while (! q.empty()) {
            while (size > 0) {
                TreeNode* head = q.front();
                q.pop();
                if (head->left) q.push(head->left);
                if (head->right) q.push(head->right);
                --size;
            }

            ++level;
            size = q.size();
        }

        return level;
    }
};

终究还是没能掌握 bfs, 写的还是和是一样, 而且我都不知道第一个 Solution 为啥 AC.

写对了程序不难，难的是写错了还能 AC，还不知道原因在哪里.