用Python实现的二叉树最近公共祖先

Question

我在Leetcode上用Python实现了一个关于二叉树的最低公共祖先（LCA）的问题：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/。但是我遇到了一个错误：TypeError: list indices must be integers or slices, not TreeNode。现在我想知道，如何在Python中用一个二维数组self.up来记录所有父节点的TreeNode。

from collections import defaultdict
import math
class Solution:
    def __init__(self):
        # self.tin=defaultdict(int)
        # self.tout=defaultdict(int)
        self.level=[0 for i in range(10**5+1)]
        self.logN=math.ceil(math.log(10**5))
        self.up=[[TreeNode(-1) for i in range(self.logN + 1)]  for j in range(10**5 + 1)]
        
    def dfs(self, root, parent):
        # self.tin[root.val]+=1
        self.up[root][0]=parent
        for i in range(1, self.logN+1):
            up[root][i]=up[ up[root][i-1] ][i-1]
        if root.left:
            self.level[root.left]=self.level[root]+1
            dfs(self, root.left, root)
        if root.right:
            self.level[root.right]=self.level[root]+1
            dfs(self, root.right, root)
        self.tout[root]+=1
        
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.dfs(root,root)
        def is_ancestor(n1, n2):
            return self.tin[n1]<=self.tin[n2] and self.tout[n1]>=self.tout[n2]
        def lca(n1, n2):
            if self.level[n1]<self.level[n2]:
                return lca(n2,n1)
            if is_ancestor(n1, n2):
                return n1
            if is_ancestor(n1, n2):
                return n2
            for i in range(self.logN, -1, -1):
                if is_ancestor(self.up[n1][i], n2)==False:
                    n1=self.up[n1][i]
            return self.up[n1][0]
        return lca(p, q)

这是我初始化up数组的方法，用来追踪当前节点的所有上层节点：self.up=[[-1 for i in range(self.logN + 1)] for j in range(105 + 1)]。然后我尝试把它改成：self.up=[[TreeNode(-1) for i in range(self.logN + 1)] for j in range(105 + 1)]。但显然，这两种方法都给我带来了同样的错误：TypeError: list indices must be integers or slices, not TreeNode。有人能帮帮我吗！！谢谢！！！

Answer 1

你可以使用一个 defaultdict。

self.up = defaultdict(lambda: [TreeNode(-1) for i in range(self.logN + 1)])

不过要注意，这并不是在二叉树中找到最近公共祖先（LCA）最简单的方法。