当前位置: 首页 > 文档资料 > LeetCode 题解 >

Tree - Binary Tree Path

优质
小牛编辑
128浏览
2023-12-01

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

  1. 1
  2. / \
  3. 2 3
  4. \
  5. 5

All root-to-leaf paths are:

  1. ["1->2->5", "1->3"]

题目翻译:
给定一棵二叉树,返回所有从根节点到叶节点的路径。

题目分析:
本题属于二叉树的遍历问题,可以用深度优先搜索来解决。

使用栈来记录遍历过程中访问过的节点。递归地访问每个节点的子节点,如果遇到叶节点,则输出记录的路径。返回上一层之前弹出栈顶元素。
C++的vector容器也能做到后进先出,所以下面的代码并没有使用std::stack类来实现。

生成输出的字符串时,可以使用std::stringstream类来完成,类似于Java和C#中的StringBuilder。

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * TreeNode *left;
  6. * TreeNode *right;
  7. * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11. public:
  12. vector<string> binaryTreePaths(TreeNode* root) {
  13. vector<string> result;
  14. if (root == nullptr) return result;
  15. vector<int> path;
  16. bfs(root, path, result);
  17. return result;
  18. }
  19. private:
  20. // 递归函数,深度优先搜索
  21. void bfs(TreeNode* node, vector<int>& path, vector<string>& result) {
  22. if (node == nullptr) return;
  23. path.push_back(node->val);
  24. if (node->left == nullptr && node->right == nullptr)
  25. result.push_back(generatePath(path));
  26. else {
  27. if (node->left != nullptr) {
  28. bfs(node->left, path, result);
  29. path.pop_back();
  30. }
  31. if (node->right != nullptr) {
  32. bfs(node->right, path, result);
  33. path.pop_back();
  34. }
  35. }
  36. }
  37. // 辅助函数,用于生成路径字符串
  38. string generatePath(vector<int> path) {
  39. stringstream ss;
  40. int i;
  41. for (i = 0; i < path.size() - 1; i++) ss << path[i] << "->";
  42. ss << path[i];
  43. return ss.str();
  44. }
  45. };