Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-bt
# 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:
"""
Problem Clarification:
Can I assume value of node in the tree is unique? No
Let's merely get the nodes from the left boundary, the right boundary, and the leaves, in counter-clockwise order.
Think about two cases:
In the beginiing, right subtree is empty.
[1,null,2,3,4]
In the beginiing, left subtree is empty.
[1,2,null,3,5]
[1,2,2,2,2]
In order to handle duplicate value in the node, we store node itsefl in the traversal order instead of node's value. Then, we can avoid put visited already node into boundary list.
Ref:
https://leetcode.com/problems/boundary-of-binary-tree/discuss/101309/Python-Straightforward-with-Explanation
"""
def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
def dfs(r):
"""find leaves"""
if not r:
return
if not r.left and not r.right:
leaves.append(r)
dfs(r.left)
dfs(r.right)
left_boundary = []
dummy = root
if not dummy.left:
# handle edge case that in the beginiing that left subtree is empty
pass
else:
while dummy:
left_boundary.append(dummy)
if dummy.left:
dummy = dummy.left
else:
dummy = dummy.right
#print ("left_boundary", left_boundary)
right_boundary = [] # we make right boundary include root node because in the end, we'll use seen hashset to avoid put visited node into boundary list
dummy = root
if not dummy.right:
# handle edge case that in the beginiing that right subtree is empty
pass
else:
while dummy:
right_boundary.append(dummy)
if dummy.right:
dummy = dummy.right
else:
dummy = dummy.left
#print ("right_boundary", right_boundary)
leaves = []
dfs(root)
#print ("leaves", leaves)
counter_clockwise_order = [root] + left_boundary + leaves + right_boundary[::-1]
#print ("counter_clockwise_order", counter_clockwise_order)
seen = set()
boundary = []
for n in counter_clockwise_order:
if n not in seen:
boundary.append(n.val)
seen.add(n)
return boundary
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment