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.
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity : O(N)
* Space complexity : O(log(N))
*/
class Solution {
public int maxDepth(TreeNode root) {
int depth = 0;
if(root == null) return depth;
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()) {
depth++;
int noOfNodes = queue.size();
for(int i = 0; i < noOfNodes; i++) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
}
return depth;
}
}
/**
* Time complexity : O(N)
* Space complexity : O(log(N))
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int leftDepth = 1 + maxDepth(root.left);
int rightDepth = 1 + maxDepth(root.right);
return (leftDepth > rightDepth)? leftDepth: rightDepth;
}
}
