java - 递归查找二叉搜索树中每个节点的总深度？

Question

我已经解决这个问题一段时间了，我不太明白其中的逻辑。假设我有一个看起来像下面这样的二叉树：

        8                    1 * 0 =  0
      /   \
     4    12                 2 * 1 =  2
    / \   / \
   2   6 10 14               4 * 2 =  8
                                    ----
                                     10

我想找到每个节点的深度并将这些数字加在一起以获得总数。我现在得到的代码看起来像这样：

private int totalDepth(Node node, int depth) 
{
    if(node == null) 
    {
        return 0;
    }

    return totalDepth(node.left, depth + 1) + totalDepth(node.right, depth + 1);
}

我认为这会在遍历右侧之前递归地为树的左侧（8 -> 4 -> 2）的每个更深的级别添加一个，但它并不完全有效。

我已经以多种方式调整了这种方法，但似乎无法确定我所缺少的。任何帮助将不胜感激。

Answer 1

您快到了：您已将左子树和右子树的结果相加，但忘记为节点本身添加结果：

return depth                              // myself
     + totalDepth(node.left, depth + 1)   // my left subtree
     + totalDepth(node.right, depth + 1); // my right subtree

Answer 2

public virtual int GetLevelById(int id)
        {
            int i = GetParentById(id);
            if (i == 0)
                return 1;
            else
                return (1 + GetLevelById(i));
        }