CODEWITHSUNDEEP
pythonalgorithmlowest-common-ancestor
y shen
y shen

Reputation: 3

LCA of a binary tree implemented in Python

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!!!

Upvotes: 0

Views: 69

Answers (1)

Unmitigated
Unmitigated

Reputation: 89214

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.

Upvotes: 0

Related Questions