题目地址
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
题目描述
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
思路
由于树是一种递归的数据结构,因此用递归去解决的时候往往非常容易,这道题恰巧也是如此,
用递归实现的代码如下:
var maxDepth = function(root) { if (!root) return 0; if (!root.left && !root.right) return 1; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); };
如果使用迭代呢? 我们首先应该想到的是树的各种遍历,由于我们求的是深度,因此
使用层次遍历(BFS)是非常合适的。 我们只需要记录有多少层即可。相关思路请查看binary-tree-traversal
关键点解析
-
队列
-
队列中用 Null(一个特殊元素)来划分每层,或者在对每层进行迭代之前保存当前队列元素的个数(即当前层所含元素个数)
-
树的基本操作- 遍历 - 层次遍历(BFS)
代码
- 语言支持:JS,C++,Python
JavaScript Code:
/* * @lc app=leetcode id=104 lang=javascript * * [104] Maximum Depth of Binary Tree */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if (!root) return 0; if (!root.left && !root.right) return 1; // 层次遍历 BFS let cur = root; const queue = [root, null]; let depth = 1; while ((cur = queue.shift()) !== undefined) { if (cur === null) { // 注意⚠️: 不处理会无限循环,进而堆栈溢出 if (queue.length === 0) return depth; depth++; queue.push(null); continue; } const l = cur.left; const r = cur.right; if (l) queue.push(l); if (r) queue.push(r); } return depth; };
C++ Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if (root == nullptr) return 0; auto q = vector<TreeNode*>(); auto d = 0; q.push_back(root); while (!q.empty()) { ++d; auto sz = q.size(); for (auto i = 0; i < sz; ++i) { auto t = q.front(); q.erase(q.begin()); if (t->left != nullptr) q.push_back(t->left); if (t->right != nullptr) q.push_back(t->right); } } return d; } };
Python Code:
class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 q, depth = [root, None], 1 while q: node = q.pop(0) if node: if node.left: q.append(node.left) if node.right: q.append(node.right) elif q: q.append(None) depth += 1 return depth
相关题目
- 102.binary-tree-level-order-traversal
- 103.binary-tree-zigzag-level-order-traversal
题目地址 https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 题目描述 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to…
LeetCode题解103.binary-tree-zigzag-level-order-traversal题目地址 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/ 题目描述 和leetcode 102 基本是一样的,思路是完全一样的。 Given a binary tree, return the zigzag level order trav…
LeetCode题解1031.maximum-sum-of-two-non-overlapping-subarrays题目地址 https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/ 题目描述 Given an array A of non-negative integers, return the maximum sum of elements in two non-overl…
LeetCode题解1020.number-of-enclaves题目地址 https://leetcode-cn.com/problems/number-of-enclaves/ 题目描述 给出一个二维数组 A,每个单元格为 0(代表海)或 1(代表陆地)。 移动是指在陆地上从一个地方走到另一个地方(朝四个方向之一)或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。 示例 1: 输入…
我的遍历遍历有什么问题? - java我正在尝试解决此问题https://oj.leetcode.com/problems/binary-tree-preorder-traversal/,即使用递归解决方案进行预遍历。编辑:整个代码:import java.util.ArrayList; import java.util.List; public class Solution { public …