104 二叉树最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

题解

从后序遍历出发。还是递归三部曲， 递归的参数，递归的终止条件以及递归的单层逻辑

递归的参数是root，返回值是boolean

递归的终止条件，当root为空时，返回高度为0

单层逻辑，找左右子树的最大深度加当前的深度（1）

var maxDepth = function(root) {
    if (!root) return 0
    const depthLeft = maxDepth(root.left)
    const depthRight = maxDepth(root.right)

    //目前深度
    // +1 表示目前这层要加1
    const currentMaxDepth = Math.max(depthLeft, depthRight) + 1

    return currentMaxDepth
};

前序遍历过程

前序遍历的过程是个回溯的过程，先左子树，然后遍历完后回到上一级然后右子树的模式。

var maxDepth = function(root) {
    var result = 0
    var preOrder = function(root, depth) {
        result = Math.max(result, depth)

        // 終止條件
        if(!root) {
            return
        }

        if(root.left) {
            preOrder(root.left, depth + 1)
        }
        if(root.right) {
            preOrder(root.right, depth + 1)
        }
    }
    if(!root) {
        return 0
    }

    //当前是1层
    preOrder(root, 1)
    return result
}

层序遍历解法

利用层序遍历就可以非常方便的获取到最大深度，只要看有多少层就知道最大的深度。

先把层序遍历的代码搬出来

var maxDepth = function(root) {
    var levelOrder = function(root) {
        const queue = []
        const result = []
        if(!root) {
            return result
        }

        queue.push(root)
        while(queue.length) {
            const size = queue.length

            const temp = []

            for(let i=0;i<size;i++) {
                const current = queue.shift()
                temp.push(current.val)
                if(current.left) {
                    queue.push(current.left)
                }
                if(current.right) {
                    queue.push(current.right)
                }
            }
            result.push(temp)
        }

        return result
    }
}

然后我们只需要替换成深度的变量来存储深度就行。

var maxDepth = function(root) {
    var levelOrderMaxDepth = function(root) {
        const queue = []
        // 拿一个变量存储最大深度
        let result = 0
        if(!root) {
            return result
        }

        queue.push(root)
        while(queue.length) {
            const size = queue.length

            result++

            for(let i=0;i<size;i++) {
                const current = queue.shift()
                //temp.push(current.val)
                if(current.left) {
                    queue.push(current.left)
                }
                if(current.right) {
                    queue.push(current.right)
                }
            }
            //result.push(temp)
        }

        return result
    }

    return levelOrderMaxDepth(root)
}