# 10 / 12

{%hackmd theme-dark %}

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


#step 1 find left nodes

#step 2 find leaves

#step 3 find right nodes


def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
    #step 1 find left nodes
    def findLeft(node, path):
        if not node:
            return
        if not node.left and not node.right:
            return
        if node.left:
            path.append(node.val)
            findLeft(node.left, path)
        elif node.right
            path.append(node.val)
            findLeft(node.right, path)
        return

    #step 2 find leaves
    def findLeaves(node, path):
        if not node:
            return
        if not node.left and not node.right:
            path.append(node.val)
            return 
        findLeaves(node.left, path)
        findLeaves(node.right, path)

    #step 3 find right nodes
     def findRight(node, path):
        if not node:
            return
        if not node.left and not node.right:
            return
        if node.right:
            path.append(node.val)
            findRight(node.right, path)
        elif node.left:
            path.append(node.val)
            findRight(node.left, path)
        return
    
    left = []
    findLeft(root.left, left)
    leavesLeft = []
    findLeaves(root.left, leavesLeft)
    leavesRight = []
    findLeaves(root.right, leavesRight)
    right = []
    findRight(root.right, right)
    
    return [root.val] + left + leavesLeft + leavesRight + right[::-1]
    
    

###### tags: `面試`