257. Binary Tree Paths

  • 36.4%

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

1
2
3
4
5
6
7
8
9
10
For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:

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

方法一;

https://discuss.leetcode.com/topic/21447/c-simple-4ms-recursive-solution

C++ simple 4ms recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void binaryTreePaths(vector<string>& result, TreeNode* root, string t) {
if(!root->left && !root->right) {
result.push_back(t);
return;
}

if(root->left) binaryTreePaths(result, root->left, t + "->" + to_string(root->left->val));
if(root->right) binaryTreePaths(result, root->right, t + "->" + to_string(root->right->val));
}

vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if(!root) return result;

binaryTreePaths(result, root, to_string(root->val));
return result;
}

方法二:

我的代码实现:

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
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(!root) return res;
vector<int> s = {root->val};
helper(root, res, s);
return res;
}

void helper(TreeNode* root, vector<string>& res, vector<int>& s){
if(!root->left && !root->right){
string t = to_string(s[0]);
for(int i=1; i<s.size(); i++)
t += "->" + to_string(s[i]);
res.push_back(t);
return;
}
if(root->left){
s.push_back(root->left->val);
helper(root->left, res, s);
s.pop_back();
}
if(root->right){
s.push_back(root->right->val);
helper(root->right, res, s);
s.pop_back();
}
s.pop_back();
}
};

https://discuss.leetcode.com/topic/22133/my-java-and-c-solution-c-4ms

My java and c++ solution,c++ 4ms

this is a simple dfs+tree question,using preorder to visit tree will be fine.

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:

vector<string> binaryTreePaths(TreeNode* root) {
vector<string> v;
if(root)
preorder(v,root,"");
return v;
}
void preorder(vector<string>& v,TreeNode* r,string t){
if(!r)
return;
if(!t.empty())
t+=("->"+to_string(r->val));
else t+=to_string(r->val);
if(r->left||r->right){
preorder(v,r->left,t);
preorder(v,r->right,t);
}else{
v.push_back(t);
}
}
};

my java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> l=new ArrayList<>();
if(root!=null)
pre(l,root,"");
return l;
}
void pre(List<String> l,TreeNode r,String s){
if(r==null)return;
if(s.isEmpty())
s+=r.val;
else s+=("->"+r.val);
if(r.left!=null||r.right!=null){
pre(l,r.left,s);
pre(l,r.right,s);
}else
l.add(s);
}
}

https://discuss.leetcode.com/topic/21559/python-solutions-dfs-stack-bfs-queue-dfs-recursively

Python solutions (dfs+stack, bfs+queue, dfs recursively).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# dfs + stack
def binaryTreePaths1(self, root):
if not root:
return []
res, stack = [], [(root, "")]
while stack:
node, ls = stack.pop()
if not node.left and not node.right:
res.append(ls+str(node.val))
if node.right:
stack.append((node.right, ls+str(node.val)+"->"))
if node.left:
stack.append((node.left, ls+str(node.val)+"->"))
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# bfs + queue
def binaryTreePaths2(self, root):
if not root:
return []
res, queue = [], collections.deque([(root, "")])
while queue:
node, ls = queue.popleft()
if not node.left and not node.right:
res.append(ls+str(node.val))
if node.left:
queue.append((node.left, ls+str(node.val)+"->"))
if node.right:
queue.append((node.right, ls+str(node.val)+"->"))
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# dfs recursively
def binaryTreePaths(self, root):
if not root:
return []
res = []
self.dfs(root, "", res)
return res

def dfs(self, root, ls, res):
if not root.left and not root.right:
res.append(ls+str(root.val))
if root.left:
self.dfs(root.left, ls+str(root.val)+"->", res)
if root.right:
self.dfs(root.right, ls+str(root.val)+"->", res)

48ms, 64.24%, May.3rd, 2016

https://leetcode.com/discuss/52020/5-lines-recursive-python

5 lines recursive Python

1
2
3
4
5
6
def binaryTreePaths(self, root):
if not root:
return []
return [str(root.val) + '->' + path
for kid in (root.left, root.right) if kid
for path in self.binaryTreePaths(kid)] or [str(root.val)]

69ms, 5.30%, 209 / 209, May.3rd, 2016

https://leetcode.com/discuss/59288/8-lines-in-python-48ms

8 lines in python,48ms

1
2
3
4
5
6
7
8
def binaryTreePaths(self, root):
if not root:
return []
if not root.left and not root.right:
return [str(root.val)]
treepaths = [str(root.val)+'->'+path for path in self.binaryTreePaths(root.left)]
treepaths += [str(root.val)+'->'+path for path in self.binaryTreePaths(root.right)]
return treepaths

谢谢你,可爱的朋友。