LeetCode:104.二叉树的最大深度
104.二叉树的最大深度-力扣（leetcode）
1.思路
递归方法来实现
理论上，深度应该从根节点计数，直到最深的叶子节点。故采用前序遍历是统一的。
高度应该从叶子节点计数，直到根节点为止。故采用后序遍历时统一的。
但，由于最大深度和最大高度是同一个数值，所以前序遍历和后续遍历结果是一致的。
但，层序遍历应该是最好理解的。
2.代码实现
递归实现
1// 递归 2class Solution { 3 public int maxDepth(TreeNode root) { 4 if (root == null) { 5 return 0; 6 } 7 int getLeft = maxDepth(root.left); 8 int getright = maxDepth(root.right); 9 return Math.max(getLeft, getright) + 1; // 遇到最底层节点进行 +1 操作， 这个过程属于回溯 10 } 11}
迭代法实现（层序遍历）
该代码通过广度优先搜索（BFS）的方式计算二叉树的最大深度。使用一个队列来存储每一层的节点，每次遍历完一层后，深度加1。直到队列为空，即遍历完整个二叉树，返回最大深度。
1class Solution { 2 public int maxDepth(TreeNode root) { 3 if (root == null) { // 如果根节点为空，返回深度为0 4 return 0; 5 } 6 Queue<TreeNode> queue = new LinkedList<>(); // 创建一个队列来存储节点 7 queue.offer(root); // 将根节点加入队列 8 int ans = 0; // 初始化深度为0 9 while (!queue.isEmpty()) { // 当队列不为空时循环 10 int size = queue.size(); // 获取当前层的节点数量 11 while (size > 0) { // 遍历当前层的所有节点 12 TreeNode node = queue.poll(); // 从队列中取出一个节点 13 if (node.left != null) { // 如果节点的左子节点不为空，将左子节点加入队列 14 queue.offer(node.left); 15 } 16 if (node.right != null) { // 如果节点的右子节点不为空，将右子节点加入队列 17 queue.offer(node.right); 18 } 19 size--; // 当前层节点数量减1 20 } 21 ans++; // 每遍历完一层，深度加1 22 } 23 return ans; // 返回最大深度 24 } 25}
3.复杂度分析
递归：
时间复杂度：O(n),需要遍历到每个节点，故为O(n)
空间复杂度：O(height),用栈存储深度，所以空间消耗为height/depth.
层序：
时间复杂度：O(n),需要遍历到每个节点，故为O(n)
空间复杂度：O(n)+O(size)+O(ans),用队列暂存，额外用到size、ans..
LeetCode:559.n叉树的最大深度
1.思路
2.代码实现
1class Solution { 2 public int minDepth(TreeNode root) { 3 if (root == null) { 4 return 0; 5 } 6 int getLeft = minDepth(root.left); 7 int getRight = minDepth(root.right); 8 // 左子树为null时 9 if (root.left == null) { 10 return getRight + 1; 11 } 12 // 右子树为null 13 if (root.right == null) { 14 return getLeft + 1; 15 } 16 // 根节点左右子树都不为null时，取两子树较小值 17 return Math.min(getLeft, getRight) + 1; 18 } 19}
3.复杂度分析
时间复杂度：O(logN/2 ✖ logN/2)
空间复杂度：O(1)，常数项存储最大深度的数值
LeetCode:111.二叉树的最小深度
111. 二叉树的最小深度 - 力扣（LeetCode）
1.思路
最小深度和最大深度思路基本一致，需要注意的是，要排除根节点左右子树为空的情况。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。叶子节点是指没有子节点的节点。
2.代码实现
1class Solution { 2 public int minDepth(TreeNode root) { 3 if (root == null) { 4 return 0; 5 } 6 int getLeft = minDepth(root.left); 7 int getRight = minDepth(root.right); 8 // 左子树为null时 9 if (root.left == null) { 10 return getRight + 1; 11 } 12 // 右子树为null 13 if (root.right == null) { 14 return getLeft + 1; 15 } 16 // 根节点左右子树都不为null时，取两子树较小值 17 return Math.min(getLeft, getRight) + 1; 18 } 19}
3.复杂度分析
时间复杂度：遍历每个节点，故为O(N)
空间复杂度：取决于递归时，栈空间的开销。最坏情况下，树呈链状，空间复杂度为O(N),平均情况下树的高度与节点数的对数呈正相关，空间复杂度为O(logN).
LeetCode:222.完全二叉树的节点个数
1.思路
2.代码实现
递归法
1// 递归实现 2class Solution { 3 public int countNodes(TreeNode root) { 4 if (root == null) { 5 return 0; 6 } 7 int leftCount = countNodes(root.left); 8 int rightCount = countNodes(root.right); 9 int sum = leftCount + rightCount + 1; 10 return sum; 11 } 12}
迭代法
1// 迭代法 2class Solution { 3 public int countNodes(TreeNode root) { 4 if (root == null) { 5 return 0; 6 } 7 Queue<TreeNode> queue = new LinkedList<>(); // 创建层序遍历的辅助队列 8 queue.offer(root); 9 int sum = 0; 10 while (!queue.isEmpty()) { 11 int size = queue.size(); 12 while (size > 0) { 13 TreeNode cur = queue.poll(); 14 15 size--; 16 sum++; 17 if (cur.left != null) { 18 queue.offer(cur.left); 19 } 20 if (cur.right != null) { 21 queue.offer(cur.right); 22 } 23 } 24 } 25 return sum; 26 } 27}
3.复杂度分析
递归法：
时间复杂度：O(logN/2 ✖ logN/2)
空间复杂度：O(N)，代码随想录给的是O(logN),存疑!
