剣指offer JZ 38-二叉木の深さ-JavaScript

1、テーマの説明

ツリーの深さを求めるツリーを入力します.
ルートノードからリーフノードまで順次通過するノード(ルート、リーフノードを含む)は、ツリーのパスを形成し、最長パスの長さはツリーの深さである.
たとえば、与えられたツリー[3,9,20,null,null,15,7]は、その最大深さ3を返します.

 3
/ \
9 20
  / \
  15 7

2、問題を解く構想

一つの規模がnの問題を求めて、まず左の規模が約n/2の問題を求めて、更に右の規模が約n/2の問題を求めます.
次に左,右の解を結合し,最終解を求める.具体的には、集計ソートを参照してください.
したがって,最終結果はmax(ヘッドノード左サブツリーの最大深さ,ヘッドノード右サブツリーの最大深さ)+1であった.

TreeDepth(TreeNode* pRoot)->int

を求めます

先求TreeDepth(pRoot->left) ->lval

更にTreeDepth(pRoot->right) ->rval

を求めます

return max(lval, rval) + 1

時間複雑度:O(n).空間複雑度:O(n),チェーンテーブルに劣化した場合

function TreeDepth(pRoot){
    if(!pRoot){
        return 0;
    }else{
        let left = TreeDepth(pRoot.left);
        let right = TreeDepth(pRoot.right);
        return Math.max(left,right)+1;
    }
}