257. 二叉树的所有路径
image-20201204194850357
道歉声明
因为最近被一道题难住了(有序数组转二叉搜索树), 所以最近打算钻研一段时间树. 也是因为很久不复习树，所以也没什么信心接招。不管做什么，持之以恒才是最重要的！ 如果，我是说如果，有人看并且看客姥爷们不开心的话，还望海涵。
思路
看题目，差不多意思就是找到最深的节点，并把路径加到数组里。所以我们需要搞清楚，什么时候该加路径了。 找到这个核心不难，当一个节点，它又没有左孩子又没有右孩子的时候，那么它肯定是个叶子节点。 我们先用深度优先遍历，会遍历到所有节点，如果遇到叶子节点，就把记录的路径添加到result数组。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: if root is None: return [] nodes = [] # 这里利用了数组的引用传递特性 self.getSub(nodes, root, '') return nodes def getSub(self, nodes, root, path): if root is not None: # 如果path为空，说明是第一层的节点 if path != "": path = "{}->{}".format(path, root.val) else: path = str(root.val) if root.left is None and root.right is None: # 说明是叶子节点 nodes.append(path) else: # 否则继续遍历 self.getSub(nodes, root.left, path) self.getSub(nodes, root.right, path)
image-20201204194835191
