首页 > 其他 > 详细

二叉树的最小高度,最大高度(深度)和宽度

时间:2017-05-13 18:40:54      阅读:395      评论:0      收藏:0      [点我收藏+]

最大高度

function getMaxHeight(root){
    if(root == null){
        return 0;
    }
    else{
        var left = getMaxHeight(root.left);
        var right = getMaxHeight(root.right);
        return 1 + Math.max(left,right);
    }
}

最小高度

function getMinHeight(root){
    if(root = null){
        return 0;
    }
    else{
        var left = getMinHeight(root.left);
        var right = getMinHeight(root.right);
        return 1 + Math.min(left,right);
    }
}

二叉树宽度

递归方法

function getMaxWidth(root){
    if(root == null){
        return 0;
    }
    else if(root.left == null && root.right == null){
        return 1;
    }
    else{
        return getMaxWidth(root.left) + getMaxWidth(root.right);
    }
}

非递归方法

function getMaxWidth(root){
    if(root == null){return 0}
    var queue = [],
        maxWidth = 1;
    queue.push(root);
    while(true){
        var levelSize = queue.length;
        if(levelSize == 0){
            break;
        }
        while(levelSize > 0){
            var node = queue.shift();
            levelSize--;
            if(node.left){
                queue.push(node.left);
            }
            if(node.right){
                queue.push(node.right);
            }
        }
        maxWidth = Math.max(maxWidth,levelSize);
    }
    return maxWidth;
}

 

二叉树的最小高度,最大高度(深度)和宽度

原文:http://www.cnblogs.com/mengff/p/6849701.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!