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

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。

它不起作用。

- Tural Gulmammadov

---

@thg435 这个问题，即使是隐含的，也相当明显，你不觉得吗？ - Bolo

其实，我只需要一个算法。因为我的代码不起作用。如果您知道解决方案，也可以提供伪代码 :P - Tural Gulmammadov

我的猜测是：“为什么它不起作用？”发帖人似乎在英语方面有些困难，所以我会放他一马。话虽如此，我不会给出代码（因为它看起来像是一份家庭作业），但我会解释他所犯的一些更明显的错误。 - Bolo

@TGulmammadov：两个选择。选项1：在一张纸上画一棵树，手动找到任何给定节点的高度。记录你的步骤。首先尝试用伪代码描述你正在做什么，然后再用Python描述。选项2：坐下来等待一些好心人为你发布代码。 - georg

你有一个它失败的例子吗？它是如何失败的？让我猜猜：它总是计算最左路径的深度，而不是任意路径的深度？ - Has QUIT--Anony-Mousse

Answer 1

你所做的不是递归，而是迭代。递归会是这样的：

(此处为代码段，请保留html标记)

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

- mata

---

返回 max(height(node.left), height(node.right)) + 1 的值大于等于1，但叶节点的高度为零。@mata 您能否澄清一下。谢谢。 - harishvc

@harishvc - 从编辑历史记录来看，我曾经使用了 return -1，这意味着叶子节点的高度为0（通常是树的高度定义方式），但是OP指定了“叶子节点的高度为1”，所以我可能因此进行了更改。 - mata

在这里，你如何区分叶节点和根节点？ - CodeYogi

叶子节点的 node.left 和 node.right 值为 None，因此递归在此结束，无需区分叶子节点、内部节点或根节点。 - mata

我可以问一个愚蠢的问题吗？我看到你正在遍历node.left和node.right，但是max函数在做什么？我没有看到高度的计数。 - Illusionist

@Illusionist - 对于任何节点，它的高度是其最大子树的高度（这就是max函数的作用）+1。对于一个叶节点，其中node.left和node.right都为None，高度将返回0，并且递归在此结束。 - mata

Answer 2

你已经得到了mata提供的解决方案，但我建议你也查看一下你的代码并理解它正在做什么：

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

这个操作会找到正确的子节点，然后再找到它的右边的子节点，以此类推。因此，这只检查“最右侧”叶子的一条路径。

对于左侧，同样的操作：

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

递归的思想在于使用相同的方法解决每个子问题。因此，如果您仅将算法应用于子树或叶子，则它仍将起作用。

另外，递归定义会调用自身（尽管可以使用循环来实现，但这超出了本文的范围）。

记住这个定义：

递归：请参见递归的定义。

;)

- Bitwise

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

- Shruti

Answer 4

def getHeight(self, root):
    if root == None:
        return -1
    else:
        return 1 + max( self.getHeight(root.left), self.getHeight(root.right) )

- Shiva7354

---

建议对您的代码如何解决提问者的问题进行解释。仅仅给出代码答案是不被赞同的。添加信息可以让访问者快速理解重要内容，更易于消化认知，并帮助访客学习并将知识应用到自己的代码中。这有利于将Q&A作为知识交流方式，而非简单的“给我代码”服务的问答形式，并且也有助于保持SO平台的高质量。 - SherylHohman

Answer 5

以下是Python完整程序：

class Node :
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def maxDepth(node):
    if node is None :
        return 0
    else :
        ldepth = maxDepth(node.left)
        rdepth = maxDepth(node.right)

        if (ldepth>rdepth):
            return ldepth +1
        else :
            return rdepth +1

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)


print "Height of tree is %d" %(maxDepth(root))

Source : here

- Akash Kandpal

Answer 6

def height(self):
    if self.root !=None:
        return self._height(self.root,0)
    else:
        return 0

def _height(self,cur_node,cur_height):
    if cur_node==None : 
         return cur_height
    left_height = self._height(cur_node.left_child,cur_height+1)
    right_height = self._height(cur_node.right_child,cur_height+1)
    return max(left_height,right_height)

- vinay kumar poosala