Boundary of Binary Tree
- 2 min read
- LC-Medium
- Binary Tree
3 years ago
Solution
- Do three steps at a time: one for left boundary, one for right, one for leaves. Look at the rules mentioned in the question correctly: for a left boundary, only consider the right child for a node if there is no left child. Otherwise, greedily add left nodes only. Skip leaf nodes. Same for right.
- You did this by yourself, don't try to memorize anything, just read the question properly.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def is_leaf(self, root):
return root.left is None and root.right is None
def get_left_boundary(self, root, left_boundary):
if root is None or self.is_leaf(root):
return []
if self.is_leaf(root):
self.leaf_nodes.append(root.val)
return []
left_boundary.append(root.val)
if root.left:
self.get_left_boundary(root.left, left_boundary)
elif root.right:
self.get_left_boundary(root.right, left_boundary)
return left_boundary
def get_leaves(self, root, leaves):
if root is None:
return []
if self.is_leaf(root):
leaves.append(root.val)
return []
self.get_leaves(root.left, leaves)
self.get_leaves(root.right, leaves)
return leaves
def get_right_boundary(self, root, right_boundary):
if root is None or self.is_leaf(root):
return []
right_boundary.append(root.val)
if root.right:
self.get_right_boundary(root.right, right_boundary)
elif root.left:
self.get_right_boundary(root.left, right_boundary)
return right_boundary
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
left_boundary = self.get_left_boundary(root.left, [])
leaves = self.get_leaves(root, [])
right_boundary = self.get_right_boundary(root.right, [])
return [root.val] + left_boundary + leaves + right_boundary[::-1]