二叉搜索树最大值

Question

我试图在二叉搜索树中找到最大值。下面给出了示例解决方案，但我想了解我的解决方案是否有问题？我对示例解决方案的问题是，它似乎检查每个节点是否不是 None 两次：一次在 "if not current.right" 中，第二次在 "while current ... current = current.right" 中，这似乎是多余的。

示例解决方案：

      def find_largest(root_node):
        current = root_node
        while current:
            if not current.right:
                return current.value
            current = current.right

我的解决方案：

      def find_largest(root_node):
        current = root_node
        if current:
            while current.right is not None:
                current = current.right
            return current.value

Question/Code 来源：Interviewcake.com

Answer 1

您的分析是正确的，示例解决方案为每个节点检查 None 两次，而您的解决方案仅检查一次，否则它们是等效的。我还要说您的解决方案更具可读性，但这有点主观。

作为增强功能，您可以通过调用函数的参数 current 而不是 root_node 来删除函数主体中的第一行。它给你一个额外的好处，因为现在参数名称并不建议你的函数只能用 root 节点作为参数来调用。事实上，它正确地找到了任何子树中的最大值。

二叉搜索树最大值

Binary search tree largest value

python

binary-tree

binary-search-tree