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.
Approach 1: DFS
I use a stack val to track the depth of the tree I am currently processing. and use a stack to store the node I am currently processing. Each time, I will first pop the node and check if it has a child. If no child just keep popping. It's actually a pre-order traversal solution with DFS.
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> val = new Stack<>();
stack.push(root);
val.push(1);
int max = 0;
while(!stack.isEmpty()){
TreeNode node = stack.pop();
int temp = val.pop();
max = Math.max(temp, max);//here to track the max value here
if(node.left != null){
stack.push(node.left);
val.push(temp + 1);
}
if(node.right != null){
stack.push(node.right);
val.push(temp + 1);//if node has two children still push temp +1 not temp++ cause they are on the same level
}
}
return max;
}
}
Approach 2: Recursion
Consider it is a tree problem, we can easily solve the depth it by recursion. More specifically is Divider and Conquer method. We use recursion to find the left subtree and right subtree to get the bigger one. and plus the root, which is 1.
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
