[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)，避免进入空的循环
    • 字符串累加放在一起做，避免多条指令