Python Iterative solution using stack


  • 3

    Idea is very simple. Just traverse the whole tree using stack. If the left child is leave, add it to the result.

    class Solution(object):
        def sumOfLeftLeaves(self, root):
            if not root: return 0
    
            s = [root]
            res = 0
            while s:
                tmp = s.pop()
                if tmp.left:
                    s.append(tmp.left)
                    if not tmp.left.left and not tmp.left.right:
                        res += tmp.left.val
                if tmp.right:
                    s.append(tmp.right)
            return res

  • 0

    Thanks for your answer, but can you give a more specific explanation?I find it really hard to catch your idea and I have several doubts.Firts, since root is a TreeNode object, why can you assign it to a list type?And when using list method pop,it should pop the last element of the list which can't have and leaves at all. So I am really confused. So could you please explain your code in detail?Thanks a lot.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.