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.
Solution 1: recursive DFS
public class Solution {
public int maxDepth(TreeNode root) {
int[] res=new int[1];
dfs(root,0,res);
return res[0];
}
private void dfs(TreeNode x, int d, int[] res) {
if (x==null) return;
if (d+1>res[0]) res[0]=d+1;
dfs(x.left,d+1,res);
dfs(x.right,d+1,res);
}
}
Solution 2: iterative BFS, use 2 queue to count the depth.
public class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> q1=new LinkedList<>();
Queue<TreeNode> q2=new LinkedList<>();
if (root==null) return 0;
int d=0;
q1.offer(root);
while (!q1.isEmpty()) {
while (!q1.isEmpty()) {
TreeNode x=q1.poll();
if (x.left!=null) q2.offer(x.left);
if (x.right!=null) q2.offer(x.right);
}
Queue<TreeNode> temp=q1;
q1=q2;
q2=temp;
d++;
}
return d;
}
}
没有评论:
发表评论