LeetCode 257. Binary Tree Paths

题目

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

For example, given the following binary tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
/ \
2 3
\
5
```
All root-to-leaf paths are:
`["1->2->5", "1->3"]`
## 分析
找出二叉树中的所有路径
## 代码

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):

# 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)

# 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

# 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

```

点评

递归的深度优先遍历版本比较好理解,每次递归的时候,传递了子树根节点,当前路径和最终结果数组,没有返回值,终止条件是,节点没有左右子树了
栈的深度优先。。。。。
队列的广度优先。。。。