题目描述
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.
解题思路
利用深度优先搜索,对每一个非空节点首先将其值加如路径中,如果该节点既没有左子树也没有又子树则表示是根节点,将当前路径存入结果中。否则递归遍历其左子树和右子树。
代码如下:
#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