Problem statement

https://leetcode.com/problems/boundary-of-binary-tree/

Solution

Just do as what is asked: we need to create left boundary, then we create right boundary. We can use smart trick: cur = cur.left or cur.right, which traverse to left children if possible and if not go to right children. Also we need to create leafs, using dfs.

Complexity

Time complexity is O(n), space complexity is O(n) as well.

Code

class Solution:
    def boundaryOfBinaryTree(self, root):
        if not root: return []
        
        left_bound = [root]
        cur = root.left
        while cur:
            left_bound.append(cur)
            cur = cur.left or cur.right
            
        right_bound = [root]
        cur = root.right
        while cur:
            right_bound.append(cur)
            cur = cur.right or cur.left
        
        self.bottom_bound = []
        def dfs(node):
            if node.left: dfs(node.left)
            if not node.left and not node.right:
                self.bottom_bound.append(node)
            if node.right: dfs(node.right)
        dfs(root)
        
        ans, seen = [], set()
        def visit(node):
            if node not in seen:
                seen.add(node)
                ans.append(node.val)
        
        for node in left_bound: visit(node)
        for node in self.bottom_bound: visit(node)
        for node in right_bound[::-1]: visit(node)
            
        return ans