如何递归地找到二叉树中节点的高度

Question

path = 0 # the lenght of the path
    while self.right != None or self.left != None:
        while self.right != None:
            self = self.right
            path = path +1 
        while self.left != None:
            self = self.left
            path = path +1
    return path

这是我查找高度的示例代码,定义为从自身到叶子的节点数量的最长路径的长度.叶节点的高度为1.

它不起作用.

Answer 1

你所做的不是递归的,它是迭代的.递归将是这样的:

def height(node):
    if node is None:
        return 0
    else:
        return max(height(node.left), height(node.right)) + 1

Answer 2

mata 为您提供了解决方案，但我建议您也查看您的代码并了解它在做什么：

    while self.right != None:
        self = self.right
        path = path +1

这会做什么？它将找到正确的孩子，然后是它的正确孩子，依此类推。所以这只会检查“最右边”叶子的一条路径。

这对左侧执行相同的操作：

   while self.left != None:
        self = self.left
        path = path +1

递归的想法是，对于每个子问题，您使用与所有其他子问题完全相同的方法来解决它。因此，如果您将算法仅应用于子树或叶子，它仍然可以工作。

此外，递归定义调用自身（尽管您可以使用循环来实现它，但这超出了此处的范围）。

记住定义：

递归：参见递归的定义。

;)

Answer 3

def height(node):
    if node is None:
        return 0
    else:
        if node.left==None and node.right==None:
            return max(height(node.left), height(node.right))+0
        else:
            return max(height(node.left), height(node.right))+1

如果您将每个增加的边视为高度。通过 hackerrank 测试用例