Python, Straightforward with Explanation


  • 0

    Let's merely get the nodes from the left boundary, the right boundary, and the leaves, in counter-clockwise order.

    To get nodes from the left boundary, we start from root.left and move left if we can, else right, until we can't move anymore. The right boundary is similar.

    To get nodes from the leaves, we DFS until we hit a leaf (until node.left and node.right are both None). We should take care to add to our stack in the order (right, left) so that they are popped in the order (left, right).

    Now armed with all the nodes we could visit, let's visit them in order. As we visit a node, we should skip over ones we've seen before (comparing node objects by pointer, not node.val), and otherwise add node.val to our answer.

    We could also rewrite this answer by calling visit(cur) directly instead of appending to left_bd_nodes, etc. to save a little space.

    if not root: return []
    
    left_bd_nodes = [root]
    cur = root.left
    while cur:
      left_bd_nodes.append(cur)
      cur = cur.left or cur.right
    
    right_bd_nodes = [root]
    cur = root.right
    while cur:
      right_bd_nodes.append(cur)
      cur = cur.right or cur.left
    
    leaf_nodes = []
    stack = [root]
    while stack:
      node = stack.pop()
      if node.right:
        stack.append(node.right)
      if node.left:
        stack.append(node.left)
      if not node.left and not node.right:
        leaf_nodes.append(node)
    
    ans = []
    seen = set()
    def visit(node):
      if node not in seen:
        seen.add(node)
        ans.append(node.val)
    
    for node in left_bd_nodes: visit(node)
    for node in leaf_nodes: visit(node)
    for node in reversed(right_bd_nodes): visit(node)
    
    return ans
    

    Note: I try to focus my editorials on the most repeatable and instructive solutions, not the most clever or short.


Log in to reply
 

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