以递归方式查找二叉搜索树中每个节点的总深度？

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