python - Easy Leetcode：BST 深度优先搜索存在堆栈溢出错误

问题描述

我正在研究 Leetcode 问题，可以在这里找到：https ://leetcode.com/problems/minimum-distance-between-bst-nodes/

问题：给定一个具有根节点的二叉搜索树 (BST)，返回树中任意两个不同节点的值之间的最小差值。

例子：

输入：root = [4,2,6,1,3,null,null] 输出：1 解释：注意 root 是一个 TreeNode 对象，而不是一个数组。

给定的树 [4,2,6,1,3,null,null] 由下图表示：

虽然这棵树的最小差异为 1，但它发生在节点 1 和节点 2 之间，也发生在节点 3 和节点 2 之间。

注意：我已经实现了前序遍历，但是我的代码遇到了堆栈溢出错误，有人可以帮忙指出逻辑错误在哪里吗？

# 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)

标签： pythonrecursionbinary-search-treedepth-first-search

在您的helper函数中，您root在递归调用中使用当前的node. 因此，您不断地为同一个节点调用方法，而不是迭代整个树，helper这就是程序陷入无限递归的原因。使用调试器单步调试代码以调查此类问题非常有帮助。

python - Easy Leetcode：BST 深度优先搜索存在堆栈溢出错误

问题描述

解决方案

推荐阅读