104. Maximum Depth of Binary Tree - cocoder39/coco39_LC GitHub Wiki
104. Maximum Depth of Binary Tree
Solution 1: dfs. time complexity is O(n) and space complexity is O(h) where h is height of tree
int maxDepth(TreeNode* root) {
if (! root) {
return 0;
}
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
Solution 2: bfs. time complexity is O(n) and space complexity is O(w) where w is width of tree
int maxDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
int depth = 0;
while (! que.empty()) {
depth++;
int sz = que.size();
for (int i = 0; i < sz; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) {
que.push(node->left);
}
if (node->right) {
que.push(node->right);
}
}
}
return depth;
}