9 
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

this is my sample code for find the Height, is defined as the length of the longest path by number of nodes from self to a leaf. The height of a leaf node is 1.

it doesn't work.

4

6 回答 6

25

您正在做的不是递归的，而是迭代的。递归将类似于：

def height(node):
    if node is None:
        return 0
    else:
        return max(height(node.left), height(node.right)) + 1
于 2012-11-10T14:05:26.697 回答
6

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

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

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

这对左侧也是如此：

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

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

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

记住定义：

递归：参见递归的定义。

;)

于 2012-11-10T14:35:47.483 回答
4 
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测试用例

于 2018-03-10T07:20:19.847 回答
2 
def getHeight(self, root):
    if root == None:
        return -1
    else:
        return 1 + max( self.getHeight(root.left), self.getHeight(root.right) )
于 2020-06-24T05:18:48.510 回答
1

这是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))

来源：这里

于 2018-01-12T13:56:20.897 回答
0 
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)
于 2019-11-06T14:00:01.390 回答