算法题练习——JS Node+python题解BM28 二叉树的最大深度

水深无声 2024-04-07 15:18 48阅读 0赞

**描述**

> 求给定二叉树的最大深度，
> 
> 深度是指树的根节点到任一叶子节点路径上节点的数量。
> 
> 最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）

> 数据范围：0≤n≤100000，树上每个节点的val满足∣val∣≤100  
> 要求： 时间复杂度 O(n)

**示例1**

> 输入：\{1,2\}
> 
> 返回值：2

**示例2**

> 输入：\{1,2,3,4,\#,\#,5\}
> 
> 返回值：3

**解析：**

> 本文有两种解法，一种是层序遍历得到最底层，一种是不断递归；
> 
>  *  层序遍历
> 
> 1.  首先判断二叉树是否为空，空树没有遍历结果。
> 2.  建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
> 3.  每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
> 4.  每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
> 5.  访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。
> 
>  *  递归
> 
> 1.  对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.
> 2.  递归分别计算左子树与右子树的深度。
> 3.  当前深度为两个子树深度较大值再加1。

**JavaScript题解：**

/*
     * function TreeNode(x) {
     *   this.val = x;
     *   this.left = null;
     *   this.right = null;
     * }
     */
    
    /**
      * 
      * @param root TreeNode类 
      * @return int整型
      */
    function maxDepth( root ) {
        // write code here
        let res = []
        if(!root) return res
        let queue = []
        queue.push(root)
        let deep = 0
        while(queue.length){
            let temp = []
            deep += 1
            let len = queue.length
            for(let i=0; i<len; i++){
                let node = queue.shift()
                temp.push(node.val)
                if(node.left) queue.push(node.left)
                if(node.right) queue.push(node.right)
            }
            res.push(temp)
        }
        return deep
    }
    module.exports = {
        maxDepth : maxDepth
    };

**或递归解法：**

--------------------

**python题解：**

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param root TreeNode类 
    # @return int整型
    #
    class Solution:
        def maxDepth(self , root: TreeNode) -> int:
            # write code here
            if not root:
                return 0
            cur = [root]
            deep = 0
            while cur:
                con = []
                deep += 1
                for i in cur:
                    if i.left:
                        con.append(i.left)
                    if i.right:
                        con.append(i.right)
                cur = con
            return deep

**或递归解法：**

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    #
    # 
    # @param root TreeNode类 
    # @return int整型
    #
    class Solution:
        def maxDepth(self , root ):
            # write code here
            if not root: return 0
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1