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

Question

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

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

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

Answer 1

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
    }
}

与updateDepth(root, 0);

通话

Answer 2

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

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);
}

或者，或者（假设 addDepth 是您的 Node class 的一部分）：

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

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

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

How to calculate depth of each node in Binary Search Tree?

java

binary-search-tree

treenode