[LeetCode python] Binary Tree Paths

http://bookshadow.com/weblog/2015/08/16/leetcode-binary-tree-paths/

题目描述：

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

For example, given the following binary tree:

1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

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

题目大意：

给定一棵二叉树，返回所有“根到叶子”的路径。

例如，给定下面的二叉树：

1
 /   \
2     3
 \
  5

所有“根到叶子”路径为：

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

解题思路：

树的遍历，DFS或者BFS均可。

Note:

1) Warning: pay attention the line:  self.ans += path,

b=[]

>>> b +=str(100),

>>> b

['100']

>>> a=[]

>>> a +=str(100)

>>> a

['1', '0', '0']

>>>"a" + '->' + "b"

'a->b'

>>> "a" + "->" + "b"

'a->b'

2) deque:

from collections import deque
class collections.deque([iterable[, maxlen]])
Returns a new deque object initialized left-to-right (using append()) with data from iterable. If iterable is not specified, the new deque is empty.

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.


popleft()
Remove and return an element from the left side of the deque. If no elements are present, raises an IndexError.

Example:

>>> d_deque=deque(['1'])

>>> d_deque

deque(['1'])

>>> d_deque.append('2')

>>> d_deque

deque(['1', '2'])

>>> d_deque.popleft()

'1'

>>> d_deque

deque(['2'])

Python代码（DFS版本）：

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

class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        self.ans = []
        if root is None:
            return self.ans
        def dfs(root, path):
            if root.left is None and root.right is None:
                self.ans += path,
            if root.left:
                dfs(root.left, path + "->" + str(root.left.val))
            if root.right:
                dfs(root.right, path + "->" + str(root.right.val))
        dfs(root, str(root.val))
        return self.ans

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

下面是一段精炼的Python DFS代码，摘自LeetCode Discuss。

链接地址：https://leetcode.com/discuss/52020/5-lines-recursive-python

To understand it better, you can refer:

https://docs.python.org/2/tutorial/datastructures.html#list-comprehensions

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

class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    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)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# The following is a translation of the above simplified code:# 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 =[]
        for kid in (root.left, root.right):
            if kid:
                for path in self.binaryTreePaths(kid):
                    #res += [str(root.val) + '->' + path] # Also Okay.
                    res.append( str(root.val) + '->' + path )
        if res != []:
            return res
        else:
            return [str(root.val)]

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Python代码（BFS版本）：

(My own version)

# 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 root == None: return []

        ans = []

        from collections import deque

        queue = deque([[root, str(root.val)]])

        while queue:

            node, path = queue.popleft()

            if node.left == None and node.right == None:

                ans += path,

                continue

            if node.left:

                queue.append([node.left,  path + "->" + str(node.left.val)])

            if node.right:

                queue.append([node.right, path + "->" + str(node.right.val)])

        return ans

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

class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        from collections import deque
        if root is None:
            return []
        queue = deque( [ [root, str(root.val)] ] )
        ans = []
        while queue:
            front, path = queue.popleft()
            if front.left is None and front.right is None:
                ans += path,
                continue
            if front.left:
                queue += [front.left, path + "->" + str(front.left.val)],
            if front.right:
                queue += [front.right, path + "->" + str(front.right.val)],
        return ans