Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# liyunrui/545. Boundary of Binary Tree.py

Created Feb 18, 2021
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
to join this conversation on GitHub. Already have an account? Sign in to comment