• 做项目（多个C++、Java、Go、测开、前端项目）
• 刷算法（两个月高强度学算法）
• 背八股（40天挑战高频面试题）

权值优势路径计数

题目链接 (opens new window)

1、构建二叉树：首先根据层序遍历的序列构建二叉树。这可以通过使用队列来实现，队列中存储当前节点及其索引，确保可以正确地将子节点添加到父节点下。

2、路径遍历：使用深度优先搜索（DFS）遍历所有从根到叶子的路径。在遍历过程中，维护一个计数器跟踪当前路径中权值为 1 和权值为 0 的节点的数量。

3、计数满足条件的路径：每当到达一个叶子节点时，检查当前路径的权值 1 的节点数量是否比权值 0 的节点数量多 1。如果满足，递增一个全局计数器。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// DFS遍历二叉树，并计算满足条件的路径数量
void countPaths(TreeNode* node, int count1, int count0, int& result) {
    if (!node) return;

    // 更新当前路径中1和0的数量
    node->val == 1 ? count1++ : count0++;

    // 检查当前节点是否为叶子节点
    if (!node->left && !node->right) {
        // 检查1的数量是否比0的数量多1
        if (count1 == count0 + 1) {
            result++;
        }
        return;
    }

    // 递归访问左右子节点
    countPaths(node->left, count1, count0, result);
    countPaths(node->right, count1, count0, result);
}

int main() {
    int N;
    cin >> N;

    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

    if (nums.empty()) {
        cout << 0 << endl;
        return 0;
    }

    // 根据层序遍历的输入构建二叉树
    queue<TreeNode*> q;
    TreeNode* root = new TreeNode(nums[0]);
    q.push(root);
    int index = 1;

    while (!q.empty() && index < N) {
        TreeNode* node = q.front();
        q.pop();

        if (index < N && nums[index] != -1) {
            node->left = new TreeNode(nums[index]);
            q.push(node->left);
        }
        index++;

        if (index < N && nums[index] != -1) {
            node->right = new TreeNode(nums[index]);
            q.push(node->right);
        }
        index++;
    }

    // 计算满足条件的路径数
    int result = 0;
    countPaths(root, 0, 0, result);

    cout << result << endl;

    return 0;
}