二叉树的结构
二叉树是比较常见的一种的一种数据结构。
首先看看二叉树的数据结构:
//由左节点和右节点以及一个节点值构成
public class TreeNode{
TreeNode leftNode;
TreeNode rightNode;
int val;
TreeNode(int val){
this.val=val;
this.leftNode=null;
this.rightNode=null;
}
}
正是由于二叉树的这个结构，所以我们常用遍历解决二叉树的相关问题。
二叉树的深度问题
二叉树的深度问题主要分为两种，最大深度和最小深度。
最大深度:即二叉树的高度
递归思路:递归跳出条件是判断一个节点是否是空，如果为空则跳出，如果不为空则加一继续递归。最后的返回值只需返回左子树和右子树中的最大值。
代码实现:
public int deepthTree(TreeNode node){
if (node==null){
return 0; //递归跳出条件
}
return Math.max(deepthTree(node.leftNode),deepthTree(node.rightNode))+1;
}非递归思路:采用二叉树的层序遍历的思想（层序遍历为我们可以采用队列进行辅助操作）。我们需要遍历每层，每遍历完一层则将level进行加一的操作。这个问题的关键在于如何知道每层是否遍历完了，我们可以定义一个初始变量cur，然后将cur和每层的进入队列的节点的size进行比较，判断是否遍历完这个层的最后一个节点。
代码实现:
public int deepthTree(TreeNode node){
//非递归实现
LinkedList<TreeNode> queue=new LinkedList<>(); //设置队列
queue.offer(node); //将根节点入队列
TreeNode bitTree=null;
int level=0;
while (!queue.isEmpty()){
int cur=0; //当每层遍历完的时候，cur恢复初始值
int length=queue.size();
while (cur<length){
bitTree=queue.poll();
cur++;
if (bitTree.leftNode!=null) {
queue.offer(bitTree.leftNode);
}
if (bitTree.rightNode!=null) {
queue.offer(bitTree.rightNode);
}
}
level++; //层数进行++
}
return level;
}最小深度
参考别人整理的思路:
思路：
1.没有根节点，那结果就是0
2.有根节点，没有左右子树，结果为1
3.没有左子树，有右子树。把右子树看成一棵新的树。
4.没有右子树，有左子树。把左子树看成一棵新的树。
5.既有左子树，又有右子树。那就把左右子树分别都看成新的树，最后比较谁的最近叶子的路径短，就取哪边。
---------------------
原文：https://blog.csdn.net/sinat_35803474/article/details/70040544
代码实现:
public int deepthTree(TreeNode node){
//<--最小深度-->
if (node==null){
return 0;
}
if (node.leftNode==null && node.rightNode==null){
return 1;
}
if (node.rightNode==null){
return deepthTree(node.leftNode)+1;
}else if (node.leftNode==null){
return deepthTree(node.rightNode)+1;
}else {
return Math.min(deepthTree(node.leftNode),deepthTree(node.rightNode))+1;
}
}