/*
* @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;
}
};
Java Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
{
return 0;
}
// 队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int res = 0;
// 按层扩展
while(!queue.isEmpty())
{
// 拿出该层所有节点，并压入子节点
int size = queue.size();
while(size > 0)
{
TreeNode node = queue.poll();
if(node.left != null)
{
queue.offer(node.left);
}
if(node.right != null)
{
queue.offer(node.right);
}
size-=1;
}
// 统计层数
res +=1;
}
return res;
}
}
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
Go Code:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// BFS
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
depth := 1
q := []*TreeNode{root, nil} // queue
var node *TreeNode
for len(q) > 0 {
node, q = q[0], q[1:] // pop
if node != nil {
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
} else if len(q) > 0 { // 注意要判断队列是否只有一个 nil
q = append(q, nil)
depth++
}
}
return depth
}
PHP Code:
/**
* 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) return 0;
$depth = 1;
$arr = [$root, null];
while ($arr) {
/** @var TreeNode $node */
$node = array_shift($arr);
if ($node) {
if ($node->left) array_push($arr, $node->left);
if ($node->right) array_push($arr, $node->right);
} elseif ($arr) {
$depth++;
array_push($arr, null);
}
}
return $depth;
}
}
