【4.7】图搜索算法-DFS和BFS解根到叶子节点数字之和

一、题目

二、解题思路

DFS思路：

        这道题目要求计算从根节点到每个叶子节点的路径所代表的数字之和。每条路径上的数字可以通过将路径上的节点值按顺序连接起来形成一个数字。遍历一棵树从根节点到叶子节点的所有路径，最容易想到的方法是使用深度优先搜索（DFS），因此这题使用DFS是最容易解决的。

        解决方式是从根节点开始，沿着路径往下走时，当前节点的值可以通过父节点的值乘以10再加上当前节点的值来计算。默认根节点的父节点的值为0。当到达叶子节点时，将叶子节点的值加到一个全局变量中。这里以示例2为例，画个图来帮助理解。

BFS思路：

三、代码实现

DFS代码：

        以例二来测试，由于输入数组 [4, 9, 0, 5, 1] 没有明确表示空节点，假设它表示的是一棵完全二叉树的前序遍历结果。如果实际的二叉树结构与假设不符，可能会导致构建的二叉树不正确。在这种情况下，需要更详细的信息来正确构建二叉树。

#include <iostream>
#include <vector>
#include <stack>using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 辅助函数：根据前序遍历数组构建二叉树
TreeNode* buildTree(vector<int>& preorder, int& index, int n) {if (index >= n) {return nullptr;}TreeNode* root = new TreeNode(preorder[index++]);root->left = buildTree(preorder, index, n);root->right = buildTree(preorder, index, n);return root;
}int sumNumbers(TreeNode* root) {// 如果根节点是空，直接返回0即可if (root == nullptr)return 0;// 两个栈，一个存储的是节点，一个存储的是节点对应的值stack<TreeNode*> nodeStack;stack<int> valueStack;// 全局的，统计所有路径的和int res = 0;nodeStack.push(root);valueStack.push(root->val);while (!nodeStack.empty()) {// 当前节点和当前节点的值同时出栈TreeNode* node = nodeStack.top();nodeStack.pop();int value = valueStack.top();valueStack.pop();if (node->left == nullptr && node->right == nullptr) {// 如果当前节点是叶子结点，说明找到了一条路径，把这条// 路径的值加入到全局变量res中res += value;} else {// 如果不是叶子节点就执行下面的操作if (node->right != nullptr) {// 把子节点和子节点的值分别加入到栈中，这里子节点的值// 就是父节点的值*10+当前节点的值nodeStack.push(node->right);valueStack.push(value * 10 + node->right->val);}if (node->left != nullptr) {nodeStack.push(node->left);valueStack.push(value * 10 + node->left->val);}}}return res;
}int main() {// 输入数组vector<int> preorder = {4, 9, 0, 5, 1};int index = 0;// 构建二叉树TreeNode* root = buildTree(preorder, index, preorder.size());// 计算路径数字之和int result = sumNumbers(root);cout << "路径数字之和: " << result << endl;return 0;
}

DFS代码精简为递归：

#include <iostream>
#include <vector>using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 辅助函数：根据前序遍历数组构建二叉树
TreeNode* buildTree(vector<int>& preorder, int& index, int n) {if (index >= n) {return nullptr;}TreeNode* root = new TreeNode(preorder[index++]);root->left = buildTree(preorder, index, n);root->right = buildTree(preorder, index, n);return root;
}// 辅助函数：计算从根到叶子节点的路径数字之和
void dfs(TreeNode* node, int currentSum, int& totalSum) {if (node == nullptr)return;// 计算当前路径的数字currentSum = currentSum * 10 + node->val;// 如果是叶子节点，将当前路径的数字加到总和中if (node->left == nullptr && node->right == nullptr) {totalSum += currentSum;return;}// 递归遍历左子树和右子树dfs(node->left, currentSum, totalSum);dfs(node->right, currentSum, totalSum);
}int sumNumbers(TreeNode* root) {int totalSum = 0;dfs(root, 0, totalSum);return totalSum;
}int main() {// 输入数组vector<int> preorder = {4, 9, 0, 5, 1};int index = 0;// 构建二叉树TreeNode* root = buildTree(preorder, index, preorder.size());// 计算路径数字之和int result = sumNumbers(root);cout << "路径数字之和: " << result << endl;return 0;
}

BFS代码：

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 辅助函数：根据前序遍历数组构建二叉树
TreeNode* buildTree(vector<int>& preorder, int& index, int n) {if (index >= n) {return nullptr;}TreeNode* root = new TreeNode(preorder[index++]);root->left = buildTree(preorder, index, n);root->right = buildTree(preorder, index, n);return root;
}int sumNumbers(TreeNode* root) {// 边界条件的判断if (root == nullptr)return 0;queue<TreeNode*> nodeQueue;queue<int> valueQueue;int res = 0;nodeQueue.push(root);valueQueue.push(root->val);while (!nodeQueue.empty()) {// 节点和节点对应的值同时出队TreeNode* node = nodeQueue.front();nodeQueue.pop();int value = valueQueue.front();valueQueue.pop();if (node->left == nullptr && node->right == nullptr) {// 如果当前节点是叶子结点，说明找到了一条路径，把这条// 路径的值加入到全局变量res中res += value;} else {// 如果不是叶子节点就执行下面的操作if (node->left != nullptr) {// 把子节点和子节点的值分别加入到队列中，这里子节点的值// 就是父节点的值*10+当前节点的值nodeQueue.push(node->left);valueQueue.push(value * 10 + node->left->val);}if (node->right != nullptr) {nodeQueue.push(node->right);valueQueue.push(value * 10 + node->right->val);}}}return res;
}int main() {// 输入数组vector<int> preorder = {4, 9, 0, 5, 1};int index = 0;// 构建二叉树TreeNode* root = buildTree(preorder, index, preorder.size());// 计算路径数字之和int result = sumNumbers(root);cout << "路径数字之和: " << result << endl;return 0;
}

        这道题目要求计算从根节点到每个叶子节点的路径所代表的数字之和。每条路径上的数字可以通过将路径上的节点值按顺序连接起来形成一个数字。我们要做的就是把这每个数字加起来。使用深度优先搜索（DFS）应该是最容易理解的，因为每条路径也可以被想象成一个链表，每个链表代表一个数字，然后把所有链表所代表的数字加起来就是这题要求的结果。