LC 0545 [M] Boundary of Binary Tree - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=F76LIKzluKE&ab_channel=HappyCoding

# 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:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        def dfs_leftmost(node):
            if not node.left and not node.right:
                return
            
            res.append(node.val) # add first
            
            if node.left: # want to go as left as possible
                dfs_leftmost(node.left)
            elif node.right: # only go right if there is no left
                dfs_leftmost(node.right)
                
        def dfs_leaves(node):
            if not node:
                return
            
            dfs_leaves(node.left)
            
            if not node.left and not node.right:
                if node != root: # make sure the leaf is not the root (single node edge case e.g. [1])
                    res.append(node.val)
                
            dfs_leaves(node.right)
            
        def dfs_rightmost(node):
            if not node.left and not node.right:
                return
            
            if node.right: # want to go as right as possible
                dfs_rightmost(node.right)
            elif node.left: # only go left if there is no right
                dfs_rightmost(node.left)
                
            res.append(node.val) # add last
        
        res = [root.val]
        
        if root.left:
            dfs_leftmost(root.left)
            
        dfs_leaves(root)
        
        if root.right:
            dfs_rightmost(root.right)
            
        return res