# 257. Binary Tree Paths 二叉树的所有路径

@TOC

## # 题目描述

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

Note: A leaf is a node with no children.

Example:

``````Input:

1
/   \
2     3
\
5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3
``````

## # 解题方法

### # 递归

java版本：

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<String>();
if(root != null){
searchNode(root, "", ans);
}
return ans;
}

public void searchNode(TreeNode root, String path, List<String> ans){
if(root.left == null && root.right == null){
}
if(root.left != null){
searchNode(root.left, path + root.val + "->", ans);
}
if(root.right != null){
searchNode(root.right, path + root.val + "->", ans);
}
}
}
``````

===========二刷

python版本：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
res = []
self.dfs(root, res, '' + str(root.val))
return res

def dfs(self, root, res, path):
if root.left == None and root.right == None:
res.append(path)
if root.left != None:
self.dfs(root.left, res, path + '->' + str(root.left.val))
if root.right != None:
self.dfs(root.right, res, path + '->' + str(root.right.val))
``````

### # 迭代

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
stack = []
res = []
stack.append((root, str(root.val)))
while stack:
node, path = stack.pop()
if not node.left and not node.right:
res.append(path)
if node.left:
stack.append((node.left, path + "->" + str(node.left.val)))
if node.right:
stack.append((node.right, path + "->" + str(node.right.val)))
return res
``````

## # 日期

2017 年 5 月 6 日 2018 年 2 月 25 日 2018 年 11 月 19 日 —— 周一又开始了