day16|二叉树的属性
相关题目
● 104.二叉树的最大深度 559.n叉树的最大深度
● 111.二叉树的最小深度
● 222.完全二叉树的节点个数
二叉树的深度与高度
如图，
二叉树的深度表示：任意一个叶子节点到根节点的距离，是从上往下计数的，因此使用前序遍历得到任意一个叶子节点的深度
二叉树的高度表示：根节点到叶子节点的距离，是从下往上计数的，因此使用后序遍历得到跟根节点到叶子节点的高度
而二叉树的最大深度即就是根节点的高度（慢慢品），我的理解：二叉树的高度表示根节点到最后一层叶子节点的距离，刚好等于二叉树的最大深度，所以卡哥才这样总结的
二叉树的最大深度
由于根节点的高度就是这棵二叉树的最大深度，因此我们使用后序遍历求解
递归实现：递归三部曲
- 确定入参：二叉树的根节点
- 结束条件：遍历节点为null时停止
- 单次循环过程：输出左子树的高度和右子树的高度，取最大值
实现过程：
public int maxDepth(Node root) {if(root == null){return 0;}int deep = 0;for (Node chrild:root.children) {int curDeep = maxDepth(chrild);deep = Math.max(deep,curDeep);}return deep+1;}
n叉树的最大深度
实现过程：
public int maxDepth(Node root) {if(root == null){return 0;}int deep = 0;for (Node chrild:root.children) {int curDeep = maxDepth(chrild);deep = Math.max(deep,curDeep);}return deep+1;}
二叉树的最小深度
这个玩意不是很好理解
得看视频回顾回顾：
先上代码
public int minDepth(TreeNode root) {//后序，求高度if (root == null) {return 0;}int leftDeep = minDepth(root.left);int rightDeep = minDepth(root.right);if(root.left == null && root.right!=null){return rightDeep+1;}if(root.left != null && root.right==null){return leftDeep+1;}return Math.min(leftDeep,rightDeep)+1;}
满二叉树的应用
完全二叉树的节点个数
见下篇文章讲解