1.二叉树的最大深度
- 什么是二叉树的深度?
根节点到最远叶子节点的最长路径上的节点数-
什么是叶子节点?
没有子节点的节点(左右孩子都为空才行)
image.png
-
用递归法,三要素:
- 确定参数和返回值
参数就root,返回深度
2.确定终止条件
如果左右节点都没有就返回
如果空节点就返回
3.确定单层递归逻辑:
先求左子树深度,再求右子树深度,取最大再+1(中间节点)
2.n叉树的最大深度
n叉树没有left,right,只有childen,所以要用for遍历.
3.二叉树的最小深度
- 前序遍历和后序遍历的区别
前序遍历用来求深度,后序遍历用来求高度.
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
二叉树的最小深度?
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。-
和求最大深度的区别
主要差别在于处理左右孩子不为空的逻辑
在这种情况下,如果求最小深度,A的右节点是不存在的,所以如果不特别考虑只有一个节点的情况的话,这个树的最小深度成了1了,也就是A自己,但是这明显不对.
而最大深度不用考虑的原因是,就算右节点不存在,影响最大深度的从来都是存在的节点, 进入递归的返回值设置的时候要
return 1+minDepth()而不是return minDepth()
4.完全二叉树的节点个数
解法一:看作普通二叉树做
解法2 用完全二叉树的性质做,
满二叉树某深度的节点个数应该是Math.pow(2,n)+1,而且满二叉树的话,全部左边的深度应该等于全部右边的深度,如果不是满二叉树,那就左边的个数加上右边的个数+1
