Question :
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.
Anwser 1 : DFS
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL) return 0;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
return l > r ? l + 1 : r + 1;
}
};
More simpe :
class Solution {
public:
int maxDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL) return 0;
return 1 + max( maxDepth(root->left), maxDepth(root->right) );
}
};
Anwser 2 : BFS in queue
class Solution {
public:
int maxDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL) return 0;
queue<TreeNode *> Q;
Q.push(root);
int count = 1;
int depth = 0;
while(!Q.empty()){
TreeNode *tmp = Q.front();
Q.pop();
count--;
if(tmp->left){
Q.push(tmp->left);
}
if(tmp->right){
Q.push(tmp->right);
}
if(count == 0){
depth++; // one row is end, add a depth
count = Q.size(); // next row count
}
}
return depth;
}
};
Anwser 3 : BFS in
stack
class Solution {
public:
int maxDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL) return 0;
stack<TreeNode*> S;
int maxDepth = 0;
TreeNode *prev = NULL;
S.push(root);
while (!S.empty()) {
TreeNode *curr = S.top();
if (prev == NULL || 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() > maxDepth)
maxDepth = S.size();
}
return maxDepth;
}
};
参考推荐:
Maximum Depth of Binary Tree
树与二叉树的深度优先与广度优先算法
分享到:
相关推荐
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a ...com.leetcode.list ...com.leetcode.string ...Maximum Depth of Binary Tree Same Tree
java lru leetcode what_the_dead_men_say 所以这只是一个 repo,我从leetcode.com存储我的问题解决方案。 二叉树 0098 Validate Binary ...Tree ...Binary ...Maximum depth of binary tree - Java Iterative
LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两...
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by ...104.二叉树的最大深度 (Maximum Depth of Binary Tree) 118.杨辉三角 (Pascal's Triangle) 119.杨辉三角 II (Pascal's Triangle)
Maximum Depth of Binary Tree Path Sum Path Sum II Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段树 Range Sum Query - Mutable ...
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-...
leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。...Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is sorted] Medium [2. Add Two Numbers]
Maximum Depth of Binary Tree 这?也太简单了吧。。一行代码,一个尾递归搞定啊。。 终于想清楚了,leetcode的AC率应该是:在线编辑、肉眼检查,提交的准确率!借助线下debug工具,有何难度可言?丝毫没有模拟在线...
[104_maximum-depth-of-binary-tree.cpp] [105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-...
maximum-depth-of-binary-tree 105 construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-...
2sum leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp ...2Sum_Data_Structure_Design.cpp ...Remove_Nth_Node_From_End_of_List.cpp ...Maximum_Depth_B