Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/26 15:40)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串767/1548 (看更多)

590. N-ary Tree Postorder Traversal ## 思路跟昨天的一樣 Iter1. 照順序加到stack, 最後再把結果reverse Iter2. child反順序加進stack, 記錄node有沒有走過, 走過才加進res ## Code Iter1 ```python class Solution: def postorder(self, root: 'Node') -> List[int]: if not root: return [] res = [] stack = [root] while stack: node = stack.pop() res.append(node.val) for child in node.children: stack.append(child) return res[::-1] ``` Iter2 ```python class Solution: def postorder(self, root: 'Node') -> List[int]: if not root: return [] res = [] stack = [(root, False)] while stack: curr, is_visited = stack.pop() if is_visited: res.append(curr.val) else: stack.append((curr, True)) for child in reversed(curr.children): stack.append((child, False)) return res ``` --- 545. Boundary of Binary Tree ## 思路建三個array存 left boundary, leaves, right boundary 回傳 [root] + left + leaves + reverse right node會有LEFT, RIGHT, MIDDLE三種type 按照題目列的case更改type recur傳node跟node的type ## Code ```python # 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: def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]: LEFT, MIDDLE, RIGHT = 1, 2, 3 left, leaf, right = [], [], [] def recur(node, n_type): if not node: return if not node.left and not node.right: leaf.append(node.val) return if n_type == LEFT: left.append(node.val) elif n_type == RIGHT: right.append(node.val) if node.left: if n_type == LEFT: recur(node.left, LEFT) elif n_type == RIGHT and not node.right: recur(node.left, RIGHT) else: recur(node.left, MIDDLE) if node.right: if n_type == RIGHT: recur(node.right, RIGHT) elif n_type == LEFT and not node.left: recur(node.right, LEFT) else: recur(node.right, MIDDLE) recur(root.left, LEFT) recur(root.right, RIGHT) return [root.val] + left + leaf + right[::-1] ``` -- http://i.imgur.com/OLvBn3b.jpg