Простой Leetcode: BST глубина поиска сначала ошибка с переполнением стека - PullRequest
Новая
       81

Простой Leetcode: BST глубина поиска сначала ошибка с переполнением стека

0 голосов
/ 20 сентября 2019

Я работаю над проблемой Leetcode, которую можно найти здесь: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Задача : задано дерево двоичного поиска (BST) с корневым узломroot, возвращает минимальную разницу между значениями любых двух разных узлов в дереве.

Пример:

Ввод: root = [4,2,6,1,3, null, null] Вывод: 1 Объяснение: Обратите внимание, что root - это объект TreeNode, а не массив.

Данное дерево [4,2,6,1,3, null, null] представлено следующей диаграммой: 

      4
    /   \
  2      6
 / \    
1   3

, хотя минимальная разница в этом дереве равна 1, она возникает между узлом 1 и узлом 2, а также между узлом 3 и узлом 2.

Примечание : Iреализовали обход предзаказа, но мой код столкнулся с ошибкой переполнения стека, может кто-нибудь помочь указать, где логическая ошибка?

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDiffInBST(self, root):
        min_value = float('inf')

        def helper(node, min_value):
            print(node.val, "and", min_value)
            # if root is None
            if not root: 
                return None

            if node.left:
                min_value = min(min_value, node.val - node.left.val)
            if node.right:
                min_value = min(min_value, node.right.val - node.val)

            helper(root.left, min_value)
            helper(root.right, min_value)

            return min_value

        helper(root, min_value)

ПОСЛЕ ИЗМЕНЕНИЙ: 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDiffInBST(self, root):
        min_value = float('inf')

        def helper(node, min_value):
            # if root is None
            if not node: 
                return node
            print(node.val, min_value)

            if (node.left):
                min_value = min(min_value, node.val - node.left.val)
            if (node.right):
                min_value = min(min_value, node.right.val - node.val)

            helper(node.left, min_value)
            helper(node.right, min_value)

            return min_value

        helper(root, min_value)

1 Ответ

1 голос
/ 20 сентября 2019

В вашей функции helper вы используете root в рекурсивном вызове вместо текущего node.Таким образом, вместо итерации всего дерева, вы постоянно вызываете метод helper для того же узла, поэтому программа застревает в бесконечной рекурсии.Для изучения таких проблем очень полезно использовать отладчик для пошагового выполнения кода.

...