代码随想录【Day16】| 104. 二叉树的最大深度、111. 二叉树的最小深度、222. 完全二叉树的节点个数

104. 二叉树的最大深度

题目链接

题目描述：
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

难点：

思路：
递归法：递归地遍历左右子树，返回较大的深度值
迭代法：使用层序遍历，结果集中的层数就是二叉树最大的深度~

时间复杂度：O()
空间复杂度：O()

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*///递归法
class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right))+1;}
}//迭代法——使用层序遍历
class Solution {List<List<Integer>> resList = new ArrayList<>();public int maxDepth(TreeNode root) {if (root == null) return 0;Deque<TreeNode> que = new ArrayDeque<>();que.addLast(root);TreeNode cur;int len;while (!que.isEmpty()) {len = que.size();List<Integer> itemList = new ArrayList<>();for (int i = 0; i < len; i++) {cur = que.pollFirst();itemList.add(cur.val);if (cur.left != null) que.addLast(cur.left);if (cur.right != null) que.addLast(cur.right);}resList.add(itemList);}return resList.size();}
}

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
  

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

有的同学一定疑惑，为什么104.二叉树的最大深度 (opens new window)中求的是二叉树的最大深度，也用的是后序遍历。

那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。

class Solution {
public:int result;void getDepth(TreeNode* node, int depth) {result = depth > result ? depth : result; // 中if (node->left == NULL && node->right == NULL) return ;if (node->left) { // 左getDepth(node->left, depth + 1);}if (node->right) { // 右getDepth(node->right, depth + 1);}return ;}int maxDepth(TreeNode* root) {result = 0;if (root == 0) return result;getDepth(root, 1);return result;}
};

可以看出使用了前序（中左右）的遍历顺序，这才是真正求深度的逻辑！

时长：
5min

收获：

可以一起做了如下两道题目：

• 104.二叉树的最大深度
• 559.n叉树的最大深度

---

111. 二叉树的最小深度

题目链接

题目描述：
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2。

难点：
递归法的单层递归逻辑

思路：
递归法：
特别注意，当左（右）子树为空，不能直接返回左右子树最小深度。

层序遍历：
逐层遍历二叉树，如果出现最小深度的叶子，那么必定是层序遍历所找到的第一个叶子。

时间复杂度：O()
空间复杂度：O()

//递归法
class Solution {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;}return Math.min(leftDepth, rightDepth)+1;}
}//层序遍历——优化：结果集可不用维护一个List，仅维护一个int即可
class Solution {List<List<Integer>> resList = new ArrayList<>();public int minDepth(TreeNode root) {if (root == null) return 0;Deque<TreeNode> que = new ArrayDeque<>();que.addLast(root);while(!que.isEmpty()) {int len = que.size();List<Integer> itemList = new ArrayList<>();for (int i = 0; i < len; i++) {TreeNode cur = que.pollFirst();if (cur.left == null && cur.right == null) {return resList.size()+1;}itemList.add(cur.val);if (cur.left != null) que.addLast(cur.left);if (cur.right != null) que.addLast(cur.right);}resList.add(itemList);}return resList.size();}
}

时长：
10min

收获：
强化递归练习

加深了层序遍历的理解

---

222. 完全二叉树的节点个数

题目链接

题目描述：
给出一个完全二叉树，求出该树的节点个数。

示例 1：

• 输入：root = [1,2,3,4,5,6]
• 输出：6

示例 2：

• 输入：root = []
• 输出：0

示例 3：

• 输入：root = [1]
• 输出：1

提示：
树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树

难点：
层序遍历必能解决，换个思路。

刚开始的思路是想拿左下的结点，一直拿到倒数第二层，这样通过完全二叉树的性质，就可以直接计算出前n-1层的个数，然后遍历最后一层就行，但是问题是：仅仅拿到某一层的首个结点，并不能遍历这一层的所有节点，必须要用队列记录该层的上一层结点。

思路：
针对普通二叉树可以使用：
递归法、层序遍历

针对完全二叉树：
利用完全二叉树的性质
向左拿到leftDepth，向右拿到rightDepth
如果leftDepth、rightDepth一致，说明是满二叉树，直接返回结果
如果不一致，那递归地遍历左右子树（左右子树可能出现满二叉树）

时间复杂度：O(log n × log n)
空间复杂度：O(log n)

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;}
}

时长：
20min

收获：
很有收获，再消化消化