Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Example 3:
Input: root = []
Output: 0
Example 4:
Input: root = [0]
Output: 1
Solution I : (Using level order traversal)
class Solution
{
public:
int maxDepth(TreeNode *root)
{
if(root == NULL){return 0;}
TreeNode *t = root;
queue<TreeNode *> q;
q.push(root);
int s = 0;
while (!q.empty())
{
int k = q.size();
while (k > 0)
{
TreeNode *p = q.front();
q.pop();
if (p->left != NULL)
{
q.push(p->left);
}
if (p->right != NULL)
{
q.push(p->right);
}
k--;
}
s++;
}
return s;
}
};
This solution is based on level order tree traversal and finding the height.
Solution II: Recursive
class Solution
{
public:
int maxDepth(TreeNode *root)
{
if(root == NULL){
return 0;
}
int ldepth = maxDepth(root->left);
int rdepth = maxDepth(root->right);
return max(ldepth,rdepth) + 1;
}
};
Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Solution
class Solution
{
public:
int minDepth(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
int ld = minDepth(root->left);
int rd = minDepth(root->right);
if (ld == 0)
{
return rd + 1;
}
else if (rd == 0)
{
return ld + 1;
}
return min(ld, rd) + 1;
}
};
