本文主要是介绍Day16:LeedCode 104.二叉树的最大深度 111.二叉树最小深度 222.完全二叉树的结点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
104. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思路:根结点最大深度=max(左子树最大深度,右子树最大深度)+1
终止条件,结点为null,该结点最大深度为0
class Solution {public int maxDepth(TreeNode root) {if(root==null)return 0;return Math.max(maxDepth(root.left),maxDepth(root.right))+1;}}111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
本题跟上题类似,但有差别
错误代码:
与上一题求最大深度比,区别在这
当左右结点都不为空时: length=1+Math.min(minDepth(root.left),minDepth(root.right))
当左节点为空时:length=minDepth(root.right)+1
当右结点为空时:length=minDepth(root.left)+1
当根节点为空时:length=0;
class Solution {public int minDepth(TreeNode root) {if(root==null)return 0;if(root.left==null){return minDepth(root.right)+1;} else if (root.right==null){return minDepth(root.left)+1;}else{return 1+Math.min(minDepth(root.left),minDepth(root.right));}}
}222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
思路:
求普通二叉树结点个数:
结点个数=左子树结点个数+右子树结点个数+1
class Solution {public int countNodes(TreeNode root) {if(root==null)return 0;return countNodes(root.left)+countNodes(root.right)+1;}
}我们可以把完全二叉树当成普通二叉树来求结点个数,但上面方法没利用完全二叉树的特性
完全二叉树的两种情况:
1.完全二叉树为满二叉树,结点个数总数= 2^树深度 - 1
2.完全二叉树不为满二叉树,但是其左子树或者右子树为满二叉树 ,满二叉树可以直接用公式计算结点个数,对于非满二叉树结点总数=左子树结点总数+右结点总数+1
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：
递归三部曲:
1.确定返回值和参数,返回结点个数int 传入结点root
2.确认结束条件:当该子树为满二叉树为直接计算该子树结点总数
当该子树为Null时,结点个数为0
3.递归逻辑:当前子树结点个数=1+ countNodes(root.left)+countNodes(root.right)
class Solution {public int countNodes(TreeNode root) {if(root==null)return 0;int left_length=0;TreeNode leftN=root.left;while(leftN!=null){leftN=leftN.left;left_length++;}int right_length=0;TreeNode rightN=root.right;while(rightN!=null){rightN=rightN.right;right_length++;}if(right_length==left_length){return (2 << right_length) - 1;}return 1+ countNodes(root.left)+countNodes(root.right);
}
}
这篇关于Day16:LeedCode 104.二叉树的最大深度 111.二叉树最小深度 222.完全二叉树的结点个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
