剑指 Offer 55 - I. 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
节点总数 <= 10000注意：本题与主站 104 题相同：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 4.3 MB, 提交时间: 2024-02-20 09:57:46
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func calculateDepth(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, cnt int) {
if node == nil {
return
}
cnt++
ans = max(ans, cnt)
dfs(node.Left, cnt)
dfs(node.Right, cnt)
}
dfs(root, 0)
return
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 45 ms, 内存消耗: 17.8 MB, 提交时间: 2024-02-20 09:56:53
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 不用全局变量
def calculateDepth(self, root: Optional[TreeNode]) -> int:
if root is None: return 0
l_depth = self.calculateDepth(root.left)
r_depth = self.calculateDepth(root.right)
return max(l_depth, r_depth) + 1
# 用全局变量
def calculateDepth2(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(node, cnt):
if node is None:
return
cnt += 1
nonlocal ans
ans = max(ans, cnt)
dfs(node.left, cnt)
dfs(node.right, cnt)
dfs(root, 0)
return ans
php 解法, 执行用时: 16 ms, 内存消耗: 16.8 MB, 提交时间: 2021-05-10 17:15:23
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root) {
if ( $root == null ) return 0;
$res = 0;
$queue = [$root];
while ( !empty($queue) ) {
$cnt = count($queue);
for ( $i = 0; $i < $cnt; $i++ ) {
$node = array_shift($queue);
if ( $node->left ) $queue[] = $node->left;
if ( $node->right ) $queue[] = $node->right;
}
$res++;
}
return $res; // 元素个数即为二叉树的深度
}
}
php 解法, 执行用时: 12 ms, 内存消耗: 17.1 MB, 提交时间: 2021-05-10 17:10:40
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root) {
if ( $root == null ) return 0;
return max($this->maxDepth($root->left), $this->maxDepth($root->right)) + 1;
}
}