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

Question

我正在处理一个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]由下图表示：

      4
    /   \
  2      6
 / \    
1   3  

虽然此树中的最小差异为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)

Answer 1

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