找到具有给定值的节点的最短路径 - 二叉树

Question

给定一个二叉树，我想找到特定值出现的深度。

def find_depth_of_val(self, root, val):
    if not root:
        return 10000000
    if root.val == val:
        return 0
    return 1 + min(self.find_node(root.right, val), self.find_node(root.left, val))

这是我的想法，你可能会看到一个疯狂的“return 10000000”，我曾经这样做过，这样如果特定路径上没有其他东西，即下一个叶子在没有找到我们想要的节点的情况下已经到达，函数知道答案不存在并且没有 return 这种可能性。

我想知道是否有更好的方法来做到这一点，一种不使用随机“return 10000000”的方法。

编辑：有人给了我一个解决方案，我将其更改为：

def find_depth_of_val(self, root, val):
    if not root:
        return None
    if root.val == val:
        return 0
    right_side = self.find_node(root.right, val)
    left_side = self.find_node(root.left, val)
    if right_side is None:
        return left_side
    elif left_side is None:
        return right_side
    else:
        return 1 + min(self.find_node(root.right, val), self.find_node(root.left, val))

在这种情况下，考虑到我们可以 returning None 或整数，我应该如何输入提示？也就是说，我仍然愿意看看是否有其他人有任何不同的解决方案设计！！

Answer 1

这看起来很奇怪，因为 find_depth_of_val 同时具有 self（一棵树）和 root（另一棵树）作为参数。此外，当您陈述问题时，您只谈论一棵树，而 self 实际上并未在您的方法中使用。

假设您在树中的值是唯一的，这里有一个解决方案。方法 returns None 如果找不到路径或深度。 Optional[int] 表示 int 或 None:

def find_depth_of_val(self, val: int) -> Optional[int]:
    if self.val == val:
        return 0
    for node in (self.left, self.right):
        if node is not None:
            depth = node.find_depth_of_val(val)
            if depth is not None:
                return depth + 1
    return None

找到具有给定值的节点的最短路径 - 二叉树

Finding Shortest Path to Node with Given Value - Binary Tree

python

binary-tree

depth