104.二叉树的最大深度

链接：104.二叉树的最大深度
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

题解 1 - c

• 编辑时间：2021-11-28
• 执行用时：4ms
• 内存消耗：7.7MB
• 编程语言：c
• 解法介绍：递归遍历每层左右子树加一。

int maxDepth(struct TreeNode* root){
    // 如果为NULL就是0
    if (!root) return 0;
    // 否则判断左右子树的最大深度 + 1
    return fmax(maxDepth (root->left), maxDepth(root->right)) + 1;
}

题解 2 - java

• 编辑时间：2020-02-21
• 内存消耗：38.8MB
• 编程语言：java
• 解法介绍：递归。

class Solution {
	public int maxDepth(TreeNode root) {
		return height(root);
	}
	public int height(TreeNode node) {
		if (node == null)
			return 0;
		return 1 + Math.max(height(node.left), height(node.right));
	}
}

题解 3 - java

• 编辑时间：2020-02-21
• 内存消耗：39.4MB
• 编程语言：java
• 解法介绍：迭代。

class Solution {
	public int maxDepth(TreeNode root) {
		if (root == null)
			return 0;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		int height = 0;
		int size = 1;
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node.left != null)
				queue.offer(node.left);
			if (node.right != null)
				queue.offer(node.right);
			if (--size == 0) {
				size = queue.size();
				height++;
			}
		}
		return height;
	}
}

题解 4 - typescript

• 编辑时间：2020-07-28
• 执行用时：88ms
• 内存消耗：40.6MB
• 编程语言：typescript
• 解法介绍：递归判断。

function maxDepth(root: TreeNode | null): number {
  const _h = (node: TreeNode | null): number =>
    node === null ? 0 : Math.max(_h(node.left), _h(node.right)) + 1;
  return _h(root);
}