题目描述
深度(叶子节点到根节点长度),最大最小深度这里不多赘述。
代码
最大深度
直接上代码:
递归法
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)return 0;
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}
}
这里用的递归的方法,分别计算根节点左右子树的最大深度,大的那一方+1就是此二叉树的最大深度。
此外使用层次遍历来统计最大深度:
迭代,层序遍历
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)return 0;
Deque<TreeNode> queue= new LinkedList<>();
int depth=0;
TreeNode cur= root;
queue.offer(cur);
while(!queue.isEmpty()){
int count = queue.size();
while(count-->0){
cur=queue.poll();
if(cur.left!=null)queue.offer(cur.left);
if(cur.right!=null)queue.offer(cur.right);
}
depth++;
}
return depth;
}
}
最小深度
这里我是用的递归方法来找到所有的叶子节点,然后用当前深度和最小深度做对比。
递归方法
import java.util.Deque;
import java.util.LinkedList;
class Solution {
int minDepth=Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
int depth=0;
if(root==null)return depth;
minDepthRecursiveMethod(root,depth+1);
return minDepth;
}
public void minDepthRecursiveMethod(TreeNode node,int depth){
if(node==null)return;
minDepthRecursiveMethod(node.left,depth+1);
minDepthRecursiveMethod(node.right,depth+1);
if((node.left==null&&node.right==null)&&depth<minDepth){
minDepth=depth;
}
}
}
迭代,层序遍历
其实这道题使用层序遍历来统计最小深度是最合适的,因为递归总是需要遍历完所有节点才结束的,层序遍历会比递归快一半左右。
给出代码
import java.util.Deque;
import java.util.LinkedList;
class Solution {
int minDepth=Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode poll = deque.poll();
if (poll.left == null && poll.right == null) {
// 是叶子结点,直接返回depth,因为从上往下遍历,所以该值就是最小值
return depth;
}
if (poll.left != null) {
deque.offer(poll.left);
}
if (poll.right != null) {
deque.offer(poll.right);
}
}
}
return depth;
}
}