Maximum Depth of Binary Tree
Question
- leetcode: Maximum Depth of Binary Tree | LeetCode OJ
- lintcode: (97) Maximum Depth of Binary Tree
Problem Statement
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.
Example
Given a binary tree as follow:
1
/ \
2 3
/ \
4 5
The maximum depth is 3.
題解 - 遞迴
樹遍歷的題目最方便的寫法自然是遞迴，不過遞迴調用的層數過多可能會導致 Stack 空間 overflow，因此需要適當考慮遞迴調用的層數。我們首先來看看使用遞迴如何解這道題，要求二叉樹的最大深度，直觀上來講使用深度優先搜索判斷左右子樹的深度孰大孰小即可，從根節點往下一層樹的深度即自增1，遇到NULL時即返回0。
由於對每個節點都會使用一次maxDepth，故時間複雜度爲 , 樹的深度最大爲 , 最小爲 , 故空間複雜度介於 和 之間。
C++
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
return max(left_depth, right_depth) + 1;
}
};
Java
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
// write your code here
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
題解 - 迭代(顯式使用 Stack)
使用遞迴可能會導致棧空間溢出，這裏使用顯式棧空間(使用堆內存)來代替之前的隱式 Stack 空間。從上節遞迴版的程式碼(先處理左子樹，後處理右子樹，最後返回其中的較大值)來看，是可以使用類似後序遍歷的迭代思想去實現的。
首先使用後序遍歷的模板，在每次迭代循環結束處比較棧當前的大小和當前最大值max_depth進行比較。
C++
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}
TreeNode *curr = NULL, *prev = NULL;
stack<TreeNode *> s;
s.push(root);
int max_depth = 0;
while(!s.empty()) {
curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right){
s.push(curr->right);
}
} else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
}
} else {
s.pop();
}
prev = curr;
if (s.size() > max_depth) {
max_depth = s.size();
}
}
return max_depth;
}
};
題解3 - 迭代(隊列)
在使用了遞迴/後序遍歷求解樹最大深度之後，我們還可以直接從問題出發進行分析，樹的最大深度即爲廣度優先搜索中的層數，故可以直接使用廣度優先搜索求出最大深度。
C++
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}
queue<TreeNode *> q;
q.push(root);
int max_depth = 0;
while(!q.empty()) {
int size = q.size();
for (int i = 0; i != size; ++i) {
TreeNode *node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
++max_depth;
}
return max_depth;
}
};
Java
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int depth = 0;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
depth++;
int qLen = q.size();
for (int i = 0; i < qLen; i++) {
TreeNode node = q.poll();
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return depth;
}
}
源碼分析
廣度優先中隊列的使用中，qLen 需要在for 循環遍歷之前獲得，因爲它是一個變量。
複雜度分析
最壞情況下空間複雜度爲 , 遍歷每一個節點，時間複雜度爲 ,
results matching ""
powered by 