美文网首页
二叉树的最大/最小深度

二叉树的最大/最小深度

作者: RichardBillion | 来源:发表于2019-12-17 14:24 被阅读0次

    给定如下二叉树, 分别返回其最大深度4, 最小深度2。

        3
       /   \
     9    20
         /      \
      15       7
          \
           4
    

    求最大深度

    按照广度遍历

    跟层级遍历类似,最后返回总数组的长度(while的次数)就是最大深度

    function maxLevel(root) {
        let arr = [];    
        if(!root) {
            return 0;
        }
        let index = 0;
        arr.push([root]);
        while(index < arr.length) {
            const nodeArr = arr[index++];
            const chilrenNodes = nodeArr.reduce((prev, cur) => {
                if(cur.left) {
                    prev.push(cur.left);
                }
                if(cur.right) {
                    prev.push(cur.right);
                }
                return prev;
            }, []);
    
            if(chilrenNodes.length) {
                arr.push(chilrenNodes);
            }
        }
        return index;
    }
    
    递归实现

    递归就比较简单了,其最大深度就是max(左子树的最大深度,右子树的最大深度) + 1;

    function maxLevel(root) {
        if(!root) {
            return 0;
        }
        return Math.max(maxLevel(root.left), maxLevel(root.right)) + 1;
    }
    

    求最小深度

    仍尝试广度遍历

    在按照层级遍历时,如果有节点为叶子节点,则当前深度就是树的最小深度。

    function minDepth(root) {
        let arr = [];
        if(!root) {
            return 0;
        }
    
        arr.push([root]);
        let min = 0;
        let index = 0;
    
        while(arr.length && !min) {
            index++;
            const nodeArr = arr.shift();
            const childrenNodes = nodeArr.reduce((prev, cur) => {
                if(!cur.left && !cur.right) {
                    min = index;
                }
                if(cur.left) {
                    prev.push(cur.left);
                }
                if(cur.right) {
                    prev.push(cur.right);
                }
                return prev;
            }, []);
            if(childrenNodes.length) {
                arr.push(childrenNodes);
            }
        }
        return min;
    }
    
    递归实现

    此处需要注意,“最小深度是从根节点到最近叶子节点的最短路径上的节点数量。”,当没有左/右子节点时,该空子节点不能参与minDepth计算。

    function minDepth(root) {
        if(!root) {
            return 0;
        }
    
        if(!root.left) {
            return minDepth(root.right) + 1;
        }
        if(!root.right) {
            return minDepth(root.left) + 1;
        }
    
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
    

    对于没有左子树或者没有右子树的情况,可以将结果统一为 minDepth(root.left)+minDepth(root.right)+1,因为空子节点的minDepth值为0,所以两者相加再加1即可,而不用再区分到底是哪个为0。

    代码可以改写为:

    function minDepth(root) {
        if(!root) {
            return 0;
        }
    
        const leftMin = minDepth(root.left);
        const rightMin = minDepth(root.right);
    
        return (!root.left || !root.right) ? leftMin + rightMin + 1 : Math.min(leftMin, rightMin) + 1;
    }
    

    相关文章

      网友评论

          本文标题:二叉树的最大/最小深度

          本文链接:https://www.haomeiwen.com/subject/ydyjnctx.html