使用递归计算树的深度

Question

我一直在尝试写一个程序，这个程序可以接收用户输入的一个整数，然后在树的每一层上把这个整数加一，使用的是递归的方法：

编辑：这是类 set_depth 的 __init__ 方法：

class BTNode(object):
    """A node in a binary tree."""

    def __init__(self, value, left=None, right=None):
        """(BTNode, int, BTNode, BTNode) -> NoneType
        Initialize this node to store value and have children left and right,
        as well as depth 0.
        """
        self.value = value
        self.left = left
        self.right = right
        self.depth = 0  # the depth of this node in a tree

    def set_depth(self, number_of_depth):
            #Set depth of root node to 0, then all of its children to 1, and so on
            child = BTNode(number_of_depth)

            if self.left is None and self.right is None:
                return self.depth
            else:
                if self.left is not None or self.right is not None:
                    self.depth += 1
                    self.set_depth(number_of_depth)
                child.left = child

但是我总是遇到最大递归深度错误。

Answer 1

你没有对number_of_depth这个参数做任何处理（没有增加它的值...）。

我猜测，BTNode(number_of_depth)在每次递归时返回的是同一个子实例，所以你没有设置结束条件。

这只是我的猜测。

试试这个：

def set_depth(self, number_of_depth):
    #Set depth of root node to 0, then all of its children to 1, and so on
    child = BTNode(number_of_depth)

    if self.left is None and self.right is None:
        return self.number_of_depth
    else:
        if self.left is not None or self.right is not None:
            self.number_of_depth += 1
            self.set_depth(number_of_depth)
        child.left = child

Answer 2

如果我没理解错的话，你是想给一个已经存在的树里的每个节点设置深度：

class BTNode(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.depth = 0

    def set_depth(self, depth):
        if self.left is not None:
            self.left.set_depth(depth+1)
        if self.right is not None:
            self.right.set_depth(depth+1)
        self.depth = depth