Python postorder traversal without recursion


  • 0
    Q
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        p = root
        s = list()
        res = 0
        summap = dict() # (<access times>, <sum>)
        while p is not None or len(s) != 0:
            while p is not None:
                s.append(p)
                summap[p] = (1, 0)
                p = p.left
            if len(s) != 0:
                cur = s[-1]
                _acnt, _sum = summap[cur]
                if _acnt == 1:
                    summap[cur] = (2, _sum)
                    if cur.right is not None:
                        p = cur.right
                else:
                    _, ls = summap.get(cur.left, (0, 0))
                    _, rs = summap.get(cur.right, (0, 0))
                    res += abs(ls - rs)
                    summap[cur] = (_acnt, cur.val + ls + rs)
                    s.pop()
                    if cur.left in summap:
                        del summap[cur.left]
                    if cur.right in summap:
                        del summap[cur.right]
                    
    
        return res

Log in to reply
 

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