1. LeetCode 104. 二叉树的最大深度559. N 叉树的最大深度
1.1 思路
- 区别深度和高度：深度是二叉树任意一个节点到跟根节点的距离（从1还是0开始取决于题意）；高度是二叉树任意一个节点到叶子节点的距离（从1还是0开始取决于题意）
- 求高度应该用后序遍历，因为我们自己数高度时是从下往上的，而后序遍历返回结果时就是从下到上的，返回给父节点，父节点就+1即可；求深度应该用前序遍历，顺序是“根左右”，从上到下，往下遍历一个就+1。往上很多题解很精简的基本都是通过后序遍历求深度，这样其实不好理解，可以这么做是因为根节点的最大高度就是其最大深度
- 确定递归函数的参数和返回值：返回值是int代表深度，参数是node
- 确定终止条件：遍历的节点为空就return 0；
- 确定单层递归的逻辑：int leftHeight=getHeight(node.left)；int rightHeight=getHeight(node.right)；int height=max(leftHeight , rightHeight)+1
1.2 代码
class solution { /** * 递归法 */ public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return Math.max(leftDepth, rightDepth) + 1; } }
class Solution { /*递归法，后序遍历求root节点的高度*/ public int maxDepth(Node root) { if (root == null) return 0; int depth = 0; if (root.children != null){ for (Node child : root.children){ depth = Math.max(depth, maxDepth(child)); } } return depth + 1; //中节点 } }
2. LeetCode 111.二叉树的最小深度
2.1 思路
- 区别好最小深度的问题，题目的定义是根节点到叶子节点的最小距离才是最小深度，这题跟求最大深度还是有挺多区别的
- 在求最大深度时我们用的是后序遍历，因为根节点的最大高度刚好就是其最大深度，现在我们求最小深度同样可以这样，因为最小高度刚好就是其最小深度
- 由于后序应该求的是高度，通过左右孩子的情况把数值返回给父节点，然后父节点根据情况做左孩子+1还是右孩子+1
- 递归函数的参数和返回值：参数就是node，主函数第一次调用就是传入root，返回值就是int深度
- 终止条件：遇到空节点就是返回0
- 单层递归的逻辑：int leftHeight=getHeight(node.left);int rightHeight=getHeight(node.right);这里容易出现误区，就像求最大深度一样，只是返回左孩子和右孩子之间的最大值+1，这是不对的，这样会把没有左孩子的左子树或者没有右孩子的右子树记录下来，这是不符合题意的
- 那么如何处理呢？判断一下。如果左子树为空右子树不为空就返回右子树的深度+1；如果左子树不为空右子树为空就返回左子树的深度+1；如果都不为空则返回两者之间的最小值+1
2.2 代码
class Solution { /** * 递归法，相比求MaxDepth要复杂点 * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量 */ public int minDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = minDepth(root.left); int rightDepth = minDepth(root.right); if (root.left == null) { return rightDepth + 1; } if (root.right == null) { return leftDepth + 1; } // 左右结点都不为null return Math.min(leftDepth, rightDepth) + 1; } }
3. LeetCode 222. 完全二叉树的节点个数
3.1 思路
- 如果这题是普通二叉树，则前中后序遍历都可以求出节点数，迭代法的层序遍历也可以。这题是完全二叉树，则尽量使用完全二叉树的特性，后序是比较简单点的
- 递归函数的参数和返回值：返回值int 节点数，传入参数node
- 终止条件：如果节点为空就返回0
- 单层递归的逻辑：因为是后序遍历，那么就先统计左子树的数量，向左递归node.left，然后再去统计右子树的数量，向右递归node.right，然后到总的就是左右相加再+1即可
- 以上都是把二叉树当做普通二叉树做的，时间复杂度O（n），以下是完全二叉树
- 我们先忽略完全二叉树的最底层，最底层以上通过深度求节点数目，即2^(忽略最底层后的深度)-1，即个数
- 如果二叉树的子树是一棵满二叉树，那么就可以通过它的深度求节点数再返回给父节点，最后再+1
- 问题是如何判断是否为满二叉树还有怎么求深度呢？我们一直往左递归求其左侧深度，然后一直往右递归求其右侧深度，如果相同则说明是满二叉树，因为这是完全二叉树，因此这种判断方式是没错的。然后再通过2^(深度)-1返回给父节点。这样就利用了完全二叉树的特性
- 终止条件：遇到空节点返回0；遇到满二叉树就返回2^(深度)-1，那么就需要通过定义个左指针一直遍历左侧，定义个右指针一直遍历右侧，最终深度相等就返回2^(深度)-1
- 单层递归逻辑：int leftNum=getNum(node.left); int rightNum=getNum(node.right); result=leftNum+rightNum+1;
3.2 代码
class Solution { /** * 针对完全二叉树的解法 * * 满二叉树的结点数为：2^depth - 1 */ public int countNodes(TreeNode root) { if (root == null) return 0; TreeNode left = root.left; TreeNode right = root.right; int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便 while (left != null) { // 求左子树深度 left = left.left; leftDepth++; } while (right != null) { // 求右子树深度 right = right.right; rightDepth++; } if (leftDepth == rightDepth) { return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0 } return countNodes(root.left) + countNodes(root.right) + 1; } }
