题目描述
题目链接:257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
例子
Input: [1,2,3,null,5]
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
Note
- A leaf is a node with no children.
解题思路
利用深度优先搜索,对每一个非空节点首先将其值加如路径中,如果该节点既没有左子树也没有又子树则表示是根节点,将当前路径存入结果中。否则递归遍历其左子树和右子树。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| #include <string> #include <vector>
class Solution { public: std::vector<std::string> binaryTreePaths(TreeNode* root) { dfs(root, ""); return paths; }
private: std::vector<std::string> paths; void dfs(TreeNode* root, std::string path) { if (!root) { return; }
if (!path.empty()) path += "->"; path += std::to_string(root->val); if (!root->left && !root->right) { paths.push_back(path); return; } dfs(root->left, path); dfs(root->right, path); } };
|
- 时间复杂度: O(n)
- 空间复杂度: O(n) 额外空间来自所需空间,递归深度为二叉树最大深度
GitHub 代码同步地址: 257.BinaryTreePaths.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions