0%

[Leetcode]257. Binary Tree Paths(C++)

题目描述

题目链接: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