Максимальная глубина бинарного дерева в питоне

Question

Я создал кортеж из двоичного дерева, и это выглядит так:

кортеж = (1,(2,(4,5,6),(7, нет,8)),(3,9,(10,11,12)))

Древовидная структура становится более ясной, применяя отступы:

 (1,  
    (2,
        (4,
            5,
            6),
        (7,
            Никто,
            8)),
    (3,
        9,
        (10,
            11,
            12)))

Я знаю, как найти максимальную глубину двоичного дерева, используя рекурсивный метод, но я пытаюсь найти максимальную глубину, используя созданный мной кортеж. Может кто-нибудь помочь мне с тем, как это сделать?

Answer 1

Рекурсивный метод:

a = (1,(2,(4,5,6),(7,None,8)),(3,9,(10,11,12)));

def depth(x):
    if(isinstance(x, int) or x == None):
        return 1;
    else:
        dL = depth(x[1]);
        dR = depth(x[2]);
        return max(dL, dR) + 1;

print(depth(a));

Идея состоит в том, чтобы определить глубину дерева, посмотрев на его левое и правое поддерево. Если у узла нет поддеревьев, возвращается глубина 1. В противном случае возвращает max(глубина справа, глубина слева) + 1

Answer 2

Вот хитрое, но довольно эффективное решение, которое будет работать, если в вашей структуре данных нет элементов, представляющих собой строку, содержащую '(' или же ')', Я бы преобразовал кортеж в строку и проанализировал ее, чтобы посчитать глубину скобок.

string = str(myTuple)

currentDepth = 0
maxDepth = 0
for c in string:
    if c == '(':
        currentDepth += 1
    elif c == ')':
        currentDepth -= 1

    maxDepth = max(maxDepth, currentDepth)

Это дает глубину в линейном времени относительно количества символов в строке, в которую был преобразован кортеж. Это число должно быть более или менее пропорционально количеству элементов плюс глубина, поэтому сложность будет примерно равна O(n + d),

Answer 3

Я решаю это с обходом порядка уровней. Если вы знаете обход порядка уровней, этот вопрос и вопрос https://leetcode.com/problems/binary-tree-right-side-view/ можно решить с помощью одной и той же техники:

      from collections import deque
class Solution:
    def max_depth(self,root):
        if not root:
            return 0
        level=0
        q=deque([root])
        while q:
            # once we exhaust the for loop, that means we traverse all the nodes in the same level
            # so after for loop increase level+=1
            for i in range(len(q)):
                node=q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level+=1
        return level

Answer 4

class Node(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
   def maxDepth(self, root):
      if not root:
          return 0
      ldepth = self.maxDepth(root.left)
      rdepth = self.maxDepth(root.right)
      return max(ldepth, rdepth) + 1