Boundary of Binary Tree

Intuition

This problem could be splitted into 3 parts, left boundary, right boundary and the leaves. The code is clear and we calculated them one by one.

Notice that when calculating the left boundary and the right boundary, we should skip those leaves. So the leaves only counts when calculating the leaves.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        left = []
        if root.left is None:
            left.append(root.val)
        else:
            self._get_left(root, left)

        right = []
        if root.right is not None:
            self._get_right(root, right)

        leaves = []
        self._get_leaves(root.left, leaves)
        self._get_leaves(root.right, leaves)

        return left + leaves + right[:0:-1]

    def _is_leaf(self, node):
        if node is None:
            return False
        return node.left is None and node.right is None

    def _get_left(self, root, left):
        current = root
        while current and not self._is_leaf(current):
            left.append(current.val)
            current = current.left if current.left else current.right

    def _get_right(self, root, right):
        current = root
        while current and not self._is_leaf(current):
            right.append(current.val)
            current = current.right if current.right else current.left

    def _get_leaves(self, node, leaves):
        if node is None:
            return
        if self._is_leaf(node):
            leaves.append(node.val)
        else:
            self._get_leaves(node.left, leaves)
            self._get_leaves(node.right, leaves)