FilesExpand file tree

 master

/

binary-tree-paths.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (46 loc) · 1.14 KB

 master

/

binary-tree-paths.py

Copy path

Top

File metadata and controls

• Code
• Blame

51 lines (46 loc) · 1.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

41

42

43

44

45

46

47

48

49

50

51

# Time: O(n * h)

# Space: O(h)

#

# 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"]

#

#

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

result, path = [], []

self.binaryTreePathsRecu(root, path, result)

return result

def binaryTreePathsRecu(self, node, path, result):

if node is None:

return

if node.left is node.right is None:

ans = ""

for n in path:

ans += str(n.val) + "->"

result.append(ans + str(node.val))

if node.left:

path.append(node)

self.binaryTreePathsRecu(node.left, path, result)

path.pop()

if node.right:

path.append(node)

self.binaryTreePathsRecu(node.right, path, result)

path.pop()