https://leetcode.com/problems/binary-tree-paths/
Binary Tree Paths
Total Accepted: 15076 Total Submissions: 68979 Difficulty: Easy
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"]
Code1:
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ if root is None: return [] self.res = [] if root.left or root.right else [str(root.val)] if root.left: self.helper(str(root.val), root.left) if root.right: self.helper(str(root.val), root.right) return self.res def helper(self, path, node): if node.left is None and node.right is None: self.res.append(path + "->" + str(node.val)) else: if node.left: self.helper(path+ "->" + str(node.val), node.left) if node.right: self.helper(path+ "->" + str(node.val), node.right)
Code2:
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ res = [] if root is None: return res if root.left is None and root.right is None: res.append(str(root.val)) else: if root.left: res.extend([str(root.val) + "->" + p for p in self.binaryTreePaths(root.left)]) if root.right: res.extend([str(root.val) + "->" + p for p in self.binaryTreePaths(root.right)]) print res return res
Code 1 is more optimized than code 2 in that code 2 will always return `res` list as result hence waste a lot of space. All in all it is just a DFS algorithm.