104 Maximum Depth of Binary Tree 二叉樹(shù)的最大深度
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.
題目描述:
給定一個(gè)二叉樹(shù)盖桥，找出其最大深度。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)题翻。
說(shuō)明： 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)揩徊。
示例:
給定二叉樹(shù) [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思路:
主體思想是采用DFS(深度優(yōu)先搜索)
- 遞歸, 最大深度是左右子樹(shù)中的較大值, 每次遞歸子節(jié)點(diǎn)的時(shí)候 +1
- 迭代, 采用堆棧, 逐層掃描, 每到新的一層 +1
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n), 其中 n為樹(shù)中的結(jié)點(diǎn)數(shù), 因?yàn)槊總€(gè)結(jié)點(diǎn)都要訪問(wèn)一次
深度優(yōu)先搜索算法（英語(yǔ)：Depth-First-Search塑荒，DFS）是一種用于遍歷或搜索樹(shù)或圖的算法
沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)熄赡，盡可能深的搜索樹(shù)的分支。
當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過(guò)袜炕，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)本谜。
這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。
如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)偎窘，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過(guò)程乌助，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問(wèn)為止。屬于盲目搜索陌知。
步驟:
- 首先將根節(jié)點(diǎn)放入堆棧中他托。
- 從堆棧中取出第一個(gè)節(jié)點(diǎn)，并檢驗(yàn)它是否為目標(biāo)仆葡。如果找到目標(biāo)赏参，則結(jié)束搜尋并回傳結(jié)果。否則將它某一個(gè)尚未檢驗(yàn)過(guò)的直接子節(jié)點(diǎn)加入堆棧中沿盅。
- 重復(fù)步驟2把篓。
- 如果不存在未檢測(cè)過(guò)的直接子節(jié)點(diǎn)。將上一級(jí)節(jié)點(diǎn)加入堆棧中腰涧。重復(fù)步驟2韧掩。
- 重復(fù)步驟4。
- 若堆棧為空窖铡，表示整張圖都檢查過(guò)了——亦即圖中沒(méi)有欲搜尋的目標(biāo)疗锐。結(jié)束搜尋并回傳“找不到目標(biāo)”。
代碼:
C++:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/**
* 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) return 0;
queue<TreeNode*> q;
q.push(root);
int result = 0;
while (!q.empty())
{
int n = q.size();
while (n-- > 0)
{
TreeNode* cur = q.front();
q.pop();
if (cur -> left) q.push(cur -> left);
if (cur -> right) q.push(cur -> right);
}
++result;
}
return result;
}
};
Java:
/**
* 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) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 if root else 0
