題目

思路與錯誤記錄

1.二叉樹的數據結構與初始化

1.1數據結構

1.2 初始化

根據列表，順序存儲構建二叉樹

def build_tree(nodes, index=0):# idx是root開始的索引# 1. 如果>len()說明是原先就沒有# 2. 節點創建結束if index >= len(nodes) or nodes[index] is None:return None# l_idx =  2*root_idx + 1# r_idx =  2*root_idx + 2root = TreeNode(nodes[index])root.left = build_tree(nodes, 2 * index + 1)root.right = build_tree(nodes, 2 * index + 2)return root

2.解題

首先確定LRD的遍歷順序
其次確定回溯的可能，找到指定元素之后，回溯返回來【確定是遞歸問題】，情況有：

1. 在root返回
2. 在一邊返回

• 左邊
  （1）有一個節點是祖先
  （2）上面是祖先
• 右邊
  同左

3. 在兩邊返回
   這情況說明是兩個查找元素分布在root的兩側，因此祖先return root

在代碼實現的時候需要注意順序

遞歸的過程實例【情況2】：
不是指定元素的那條回溯是null，找到指定元素的向上返回，其上一層返回的就是他們的祖先節點

最后LRD遍歷完所有，左邊返回值【祖先節點】，右邊是null。所以只要return回來2并作為結果就行了

完整代碼

## 并查集做。但是感覺是二叉樹+遞歸# 定義二叉樹節點類
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def lowestCommonAncestor(self, root, p, q):# 0. 如果root為空，或者root就是p或q，直接返回rootif not root or root == p or root == q:return root# 遞歸查找左子樹和右子樹left = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)# 1.左右都返回，root是祖先if left and right:return root# 2.一邊返回【還可以添加終止查找吧？如果都在左可以直接不要找右邊了】if not left:return rightif not right:return left# return left if left else right# 根據列表，順序存儲構建二叉樹
def build_tree(nodes, index=0):# idx是root開始的索引# 1. 如果>len()說明是原先就沒有# 2. 節點創建結束if index >= len(nodes) or nodes[index] is None:return None# l_idx =  2*root_idx + 1# r_idx =  2*root_idx + 2root = TreeNode(nodes[index])root.left = build_tree(nodes, 2 * index + 1)root.right = build_tree(nodes, 2 * index + 2)return root# 測試用例
if __name__ == "__main__":# 示例1nodes1 = [3,5,1,6,2,0,8,None,None,7,4]root1 = build_tree(nodes1)p1 = root1.left  # 5q1 = root1.right  # 1solution = Solution()lca1 = solution.lowestCommonAncestor(root1, p1, q1)

今天做了什么

• 530 起床
• 630 跑步【6k】
• 830工位，1題&八股
• 1130吃飯&打電話，1230看小說 【沒打電話，自己玉玉去了】
• 1400 代碼 【自閉】
• 下樓把衣服帶出來洗
• 1930 寫東西/看論文 【打了3h羽毛球，一晚上都輸！】
• 2330 前睡覺 【熬夜惡魔了】