Leetcode 257: Binary Tree Path

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.

 

Leave a comment

Your email address will not be published. Required fields are marked *