思路与错误记录

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的遍历顺序
其次确定回溯的可能，找到指定元素之后，回溯返回来【确定是递归问题】，情况有：

在root返回
在一边返回

左边
（1）有一个节点是祖先
（2）上面是祖先
右边
同左

在两边返回
这情况说明是两个查找元素分布在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)