[LeetCode] 257. Binary Tree Paths | 二叉树输出路径

题目来源: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
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]

思路

  • 二叉树的遍历:先序遍历,递归调用
  • 解决好走过路径的记录和回退
  • C语言处理字符的操作不太便捷,试着用Python写这道题

时间复杂度:O(n), 空间复杂度O(logn)

源码

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
//257. Binary Tree Paths
//LeetCode: https://leetcode.com/problems/binary-tree-paths/
class Solution(object):
def getPath(self, node):
self.path.append(node)
if(node.left is None and node.right is None):
one_path = ""
one_path += str(self.path[0].val)
for i in self.path[1:]:
one_path = one_path + "->" + str(i.val)
self.res.append(one_path)
if(node.left is not None):
self.getPath(node.left)
if(node.right is not None):
self.getPath(node.right)
self.path.pop()
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
self.res = []
self.path = []
if(root is None):
return self.res
self.getPath(root)
return self.res

运行结果

209 / 209 test cases passed.
Status: Accepted
Runtime: 60 -> 58 -> 50 -> 48 ms
Submitted: 13 minutes ago

You are here! Your runtime beats 64.24% of csubmissions.

总结

  1. 递归的方式遍历二叉树,调整节点输出的位置便实现了不同的遍历方式
  2. Python的执行效率相比C还是差了不少,C的话应该在10ms内
  3. Python写的好处是List可以实现栈的功能,确实方便
  4. 改进三版本后代码跑48ms,看别人Python也有写到40ms左右的,如何实现的?
    • 删除执行一次的if判断
    • 增加if(node.left is not None),避免进入空的循环
    • 字符串累加放在一起做,避免多条指令