LCA of a binary tree implemented in Python

Question

I have implemented LCA of a binary tree problem on Leetcode using Python: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ But I got error: TypeError: list indices must be integers or slices, not TreeNode. I am wondering how do I keep track of all parents treenode in self.up 2d array in Python.

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)

This is how I initialized up array to track all the upper level nodes of a current node: self.up=[[-1 for i in range(self.logN + 1)] for j in range(105 + 1)] and then I tried to change it to: self.up=[[TreeNode(-1) for i in range(self.logN + 1)] for j in range(105 + 1)] But apparently, both of them gave me the same error: TypeError: list indices must be integers or slices, not TreeNode. Can someone please help!!thank you!!!

You could use self.up = defaultdict(lambda: [TreeNode(-1) for i in range(self.logN + 1)]), but you really don't need such a complicated method to find the LCA in a binary tree. — Unmitigated
– Unmitigated, Commented Mar 31, 2024 at 1:53

Unmitigated · Accepted Answer · 2024-03-31 04:22:04Z

0

You could use a defaultdict.

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

Note, however, that this is not the simplest way to find the LCA in a binary tree.

answered Mar 31, 2024 at 4:22

Unmitigated

91.4k12 gold badges102 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

LCA of a binary tree implemented in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related