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）の右側をトラバースする前に、各レベルの深さまで再帰的に1つ追加されると思いましたが、完全には機能しません。

私はこの方法をいくつもの方法で微調整しましたが、私が欠けているものを突き止めることができないようです。どんな助けでも大歓迎です。

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