Python solution, recursive dfs ~20 lines.


  • 2
    T
    def boundaryOfBinaryTree(self, root):
        # The main idea is to carry the flag isleft and isight
        # in the dfs steps to help decide when to add node
        # values to the boundary array.
        if not root: return []
        boundary = [root.val]
        def dfs(root, isleft, isright):
            if root:
                # append when going down from the left or at leaf node
                if (not root.left and not root.right) or isleft:
                    boundary.append(root.val)
                
                if root.left and root.right:
                    dfs(root.left, isleft, False)
                    dfs(root.right, False, isright)
                else:
                    dfs(root.left,  isleft, isright)
                    dfs(root.right, isleft, isright)
                
                # append to boundary when coming up from the right
                if (root.left or root.right) and isright:
                    boundary.append(root.val)
        
        dfs(root.left, True, False)
        dfs(root.right, False, True)
        return boundary

Log in to reply
 

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