LeetCode二叉树LCA实现报错TypeError，求up数组父节点追踪方案

错误根源 #

你触发的TypeError: list indices must be integers or slices, not TreeNode，是因为直接用TreeNode实例作为列表self.up、self.level的索引——列表仅支持整数/切片作为索引，不能用对象实例。

代码中的具体问题及修正 #

1. 列表索引误用：所有用节点实例作为列表索引的地方，必须替换为节点的val属性（假设节点val唯一，符合LeetCode题目约束）。比如self.up[root][0]改为self.up[root.val][0]，self.level[root.left]改为self.level[root.left.val]。
2. 未正确引用类成员：dfs方法中直接写up、dfs会导致全局变量查找失败，必须加上self.前缀，比如self.up、self.dfs。
3. 注释变量却被调用：self.tin和self.tout被注释，但is_ancestor函数依赖这两个变量，必须取消注释并正确初始化。
4. 冗余逻辑：lca函数中重复判断is_ancestor(n1, n2)，第二个判断完全多余，需要删除。
5. 初始化优化：固定大小的列表self.up对非连续val的节点不友好，改用字典存储跳跃表更灵活，避免空间浪费。

修正后的完整代码 #

from collections import defaultdict
import math
class Solution:
    def __init__(self):
        self.tin = defaultdict(int)
        self.tout = defaultdict(int)
        self.level = defaultdict(int)
        self.logN = math.ceil(math.log(10**5))
        # 用字典存储每个节点的跳跃表，键为节点val，值为对应层级的父节点val
        self.up = defaultdict(lambda: [-1]*(self.logN + 1))
        self.time = 0
        
    def dfs(self, root, parent_val):
        self.time += 1
        self.tin[root.val] = self.time
        self.up[root.val][0] = parent_val
        # 预处理跳跃表
        for i in range(1, self.logN + 1):
            self.up[root.val][i] = self.up[self.up[root.val][i-1]][i-1]
        if root.left:
            self.level[root.left.val] = self.level[root.val] + 1
            self.dfs(root.left, root.val)
        if root.right:
            self.level[root.right.val] = self.level[root.val] + 1
            self.dfs(root.right, root.val)
        self.time += 1
        self.tout[root.val] = self.time
        
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.level[root.val] = 0
        self.dfs(root, root.val)
        
        def is_ancestor(n1_val, n2_val):
            return self.tin[n1_val] <= self.tin[n2_val] and self.tout[n1_val] >= self.tout[n2_val]
        
        def lca(n1_val, n2_val):
            # 保证n1在更深的层级
            if self.level[n1_val] < self.level[n2_val]:
                return lca(n2_val, n1_val)
            # 如果n1是n2的祖先，直接返回n1
            if is_ancestor(n1_val, n2_val):
                return self.find_node(root, n1_val)
            # 向上跳跃n1，直到找到n2的祖先
            for i in range(self.logN, -1, -1):
                if not is_ancestor(self.up[n1_val][i], n2_val):
                    n1_val = self.up[n1_val][i]
            return self.find_node(root, self.up[n1_val][0])
        
        # 辅助函数：通过val查找节点
        def find_node(node, target_val):
            if not node:
                return None
            if node.val == target_val:
                return node
            left = find_node(node.left, target_val)
            return left if left else find_node(node.right, target_val)
        
        return lca(p.val, q.val)

额外说明 #

• 改用defaultdict存储level和up，避免固定列表的空间浪费和索引越界问题；
• 添加find_node辅助函数，因为最终需要返回TreeNode实例，而我们预处理存储的是节点val；
• 修正了tin和tout的时间戳赋值逻辑，确保正确记录节点的进入和退出时间。

内容的提问来源于stack exchange，提问作者y shen