如何递归求二叉树中节点的高度

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

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测试用例

Answer 3

mata给了你解决方案，但我建议你也看看你的代码，了解它在做什么：

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

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

这对左侧也一样：

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

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

此外，递归定义调用自身（虽然可以通过循环实现，但这超出了此处的范围）。

记住定义：

递归：参见递归的定义。

；）