leetcode-bt

545. Boundary of Binary Tree.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    Problem Clarification:
        Can I assume value of node in the tree is unique? No
    Let's merely get the nodes from the left boundary, the right boundary, and the leaves, in counter-clockwise order.
    
    Think about two cases:
        In the beginiing, right subtree is empty.
        [1,null,2,3,4]
        In the beginiing, left subtree is empty.
        [1,2,null,3,5]
        [1,2,2,2,2]
    In order to handle duplicate value in the node, we store node itsefl in the traversal order instead of node's value. Then, we can avoid put visited already node into boundary list.
    
    Ref:
        https://leetcode.com/problems/boundary-of-binary-tree/discuss/101309/Python-Straightforward-with-Explanation
    """
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        def dfs(r):
            """find leaves"""
            if not r:
                return 
            if not r.left and not r.right:
                leaves.append(r)
            dfs(r.left)
            dfs(r.right)
            
        left_boundary = []
        dummy = root
        if not dummy.left:
            # handle edge case that in the beginiing that left subtree is empty
            pass
        else:
            while dummy:
                left_boundary.append(dummy)
                if dummy.left:
                    dummy = dummy.left
                else:
                    dummy = dummy.right
            
        #print ("left_boundary", left_boundary)
        right_boundary = [] # we make right boundary include root node because in the end, we'll use seen hashset to avoid put visited node into boundary list
        dummy = root
        if not dummy.right:
            # handle edge case that in the beginiing that right subtree is empty
            pass
        else:
            while dummy:
                right_boundary.append(dummy)
                if dummy.right:
                    dummy = dummy.right
                else:
                    dummy = dummy.left
            
        #print ("right_boundary", right_boundary)
        leaves = []
        dfs(root)
        #print ("leaves", leaves)
        counter_clockwise_order = [root] + left_boundary + leaves + right_boundary[::-1]
        #print ("counter_clockwise_order", counter_clockwise_order)
        seen = set()
        boundary = []
        for n in counter_clockwise_order:
            if n not in seen:
                boundary.append(n.val)
                seen.add(n)
        return boundary