第55题 – 二叉树的深度

作者: 周伟林 分类: 剑指offer 发布时间: 2018-05-04 11:08

题目描述

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

解题思路

思路1(自顶向下 -> 递归):

二叉树的深度是其左右子树的深度加一中更大的那颗。

思路2

层序遍历,并统计层数。

JavaScript实现

解法1: 递归左右子树

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

解法2: 非递归

function TreeDepth(pRoot)
{
    if(pRoot === null)    return 0;
    let qu = [pRoot], depth = 0, cnt = 0, nextCnt = 1;
    while(qu.length > 0){
        let p = qu.shift();
        cnt++;
        if(p.left !== null) qu.push(p.left);
        if(p.right !== null) qu.push(p.right);
        if(cnt === nextCnt){    // nextCnt为一层的宽度
            nextCnt = qu.length;
            cnt = 0;
            depth++;
        }
    }
    return depth;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注