Problem
Find the maximum depth of a given binary tree.
Definition of maximum depth: find the longest path from the root node down to the farthest leaf node, the total number of nodes along the path is the maximum depth.
Definition of leaf node: a node with no children.
Example:
Given the following binary tree,
3
/ \
7 10
/ \
25 0
the answer is 3. The longest root to leaf path has 3 nodes, thus maximum depth is 3.
Solution
Using trace back, we can easily find the depth at leaf.
public class MaxDepth {
int max = 0;
public void maxDep(Node root, int size) {
if(root == null) {
max = Math.max(max, size);
return;
}
maxDep(root.left, size+1);
maxDep(root.right, size+1);
}
public static void main(String...args) {
MaxDepth md = new MaxDepth();
Node root = new Node(3, new Node(7, null, null), new Node(10, new Node(25, null, null), new Node(0, null, null)));
md.maxDep(root, 0);
System.out.println(md.max);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
int max = 0;
public void maxDep(Node root, int size) {
if(root == null) {
max = Math.max(max, size);
return;
}
maxDep(root.left, size+1);
maxDep(root.right, size+1);
}
public static void main(String...args) {
MaxDepth md = new MaxDepth();
Node root = new Node(3, new Node(7, null, null), new Node(10, new Node(25, null, null), new Node(0, null, null)));
md.maxDep(root, 0);
System.out.println(md.max);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time cost O(N), space cost O(logN) to O(N) depends on the tree is balanced or not.
