Binary Tree Paths
LeetCode 257
DFS
# 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):
"""
:type root: TreeNode
:rtype: List[str]
"""
self.res = []
def dfs(root, path):
if not root.left and not root.right:
self.res.append(path+str(root.val))
if root.left:
# 第二次複習少加了"path" (path+str(root.val)+"->")
# 出來會少個root很神奇
dfs(root.left, path+str(root.val)+"->")
if root.right:
dfs(root.right, path+str(root.val)+"->")
dfs(root,"")
return self.res
Stack
# 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):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
stack = [(root, "")]
res = []
while stack:
node, strr = stack.pop()
if node:
if not node.left and not node.right:
res.append(strr+str(node.val))
if node.left:
stack.append((node.left, strr + str(node.val) + "->"))
if node.right:
stack.append((node.right, strr + str(node.val) + "->"))
return res
Last updated