啊啊學語

題目 Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. 直覺解 構想： 用 dictionary 儲存已經複製好的節點，因為節點的 val 和節點的編號是一樣的，所以就用 val 的值當作 key。用 waiting_stack 儲存待複製的節點。 while 迴圈：從 waiting_stack 裡拿出節點，先複製這個節點。然後迭代該節點的鄰居，把鄰居複製一份，把複製的鄰居 append 到 neighbors 裡；因為鄰居的鄰居還沒有被複製，所以需要把鄰居放進去 waiting_stack。 python 3 實作： def cloneGraph(self, node: 'Node') -> 'Node':     if not node:         return None     def clone_node(node):         if not clonedNodes.get(node.val):             clonedNodes[node.val] = Node(node.val)         return clonedNodes[node.val]     clonedNodes = {}     waiting_stack = [node]     while waiting_stack:         current = waiting_s...

題目 Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). 直覺解 構想： 把第 n 層的節點由左而右存到 list 裡。要計算 n+1 層有哪些節點時，就用 for 迴圈迭代第 n 層的節點，每一圈都把該節點的左節點和右節點存起來。作法跟我在 #236. Lowest Common Ancestor of a Binary Tree 時把 Tree 轉成 array 的那一步類似。 沒有用 level 之類的變數紀錄現在是 tree 的哪一層，所以在計算 n+1 層有哪些節點時，還沒算完整層之前，是先把結果暫時儲存在別的 list，算完後再一口氣把結果 append 到 ans 裡 用 flag 判斷是否該結束 while 迴圈 python 3 實作： def levelOrder(self, root: TreeNode) -> List[List[int]]:     if not root:         return []     ans = [[root.val]]     uncheckNode = [root]     isDone = False     while not isDone:         tempAns = []         tempUncheckNode = []         isDone = True         for node in uncheckNode:             if not node:       ...

題目 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” 直覺解 構想： 把 Tree 轉成 array，index 為 k 的元素，其子元素 index 為 2k+1 和 2k+2，其父元素 index 為 k-1 / 2 後無條件捨去到整數位 找出 p 和 q 在 array 中的 index 找出 p 和 q 的所有 ancestor，在 array 中的 index 找出 lowest common ancestor python 3 實作（失敗）： def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':     heap = [root]     children_unchecked = [root]     p_index = None     q_index = None     isDone = False     # 把 Tree 轉成 array     while not isDone:         isDone = True      ...