如何计算二叉搜索树中每个节点的深度？

Question

我的任务是计算每个节点的深度，并将其存储在Node类中给出的“深度”中。但是我不知道我应该如何处理这个任务。我在互联网上寻找一些示例，但没有找到任何适合我的任务的示例。这是我给定的Node类的代码：

Node
{int value; Node left, right; int depth;}

我以为我可以用类似的方法来计算树的高度，但是没有成功。有帮助吗？

Answer 1

二叉树上的大多数算法都是通过递归工作的——你检查一个基本条件，看看递归是否应该停止，然后你为左右两个孩子做你的事情，可能会积累你发现的东西。在这种情况下，

static void addDepth(Node n, int currentDepth) {
    if (n == null) return; // check base condition

    // store current depth in this node
    n.setDepth(currentDepth);

    // recursion
    addDepth(left, currentDepth+1);
    addDepth(right, currentDepth+1);
}

或者，或者（假设addDeth是您的Node类的一部分）：

void addDepth(int current) {
     depth = current;
     if (left != null) left.addDepth(current+1);
     if (right != null) right.addDepth(current+1);
}

两种版本都是等效的。在第二个版本中，我是在递归之前检查基本条件，而不是在查看节点之前（如第一个版本中所做的那样）。

Answer 2

void updateDepth(Node node, int depth)
{
    if (node != null)
    {
        node.depth = depth;
        updateDepth(node.left, depth + 1); // left sub-tree
        updateDepth(node.right, depth + 1); // right sub-tree
    }
}

使用＜code＞updateDepth（root，0）调用