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.
# 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)