Python solution Preorder + Postorder Traversal


  • 0
    Z

    The solution is using preorder + postorder traversal.

    1. Define two variables left_border and right_border
    2. If current node is left_border or a leaf node we do preorder traversal directly add the node to the result.
    3. If current node is right_border, we do postorder traversal and add this node after process left and right child nodes.
    4. One special situation is when current node is left_border [right_border] but it doesn't have left [right] child, then its right [left] child becomes left [right] border.
    class Solution(object):
        def boundaryOfBinaryTree(self, root):
            def dfs(root, left_border, right_border):
                if not root: return
                if left_border or not right_border and not (root.left or root.right):
                    res.append(root.val)
                dfs(root.left, left_border, right_border and not root.right)
                dfs(root.right, left_border and not root.left, right_border)
                if right_border:
                    res.append(root.val)
            res = root and [root.val] or []
            dfs(root and root.left, True, False)
            dfs(root and root.right, False, True)
            return res

Log in to reply
 

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