111.二叉树的最小深度
题目链接 力扣
思路
跟求104.二叉树的最大深度思想上是类似的
自上而下的思路：前序遍历，当遍历到一个叶子节点的时候，就是二叉树的最小深度
自下而上的思路：后序遍历，统计根节点到每一个叶子节点的深度，比较出最小值
二叉树的最小深度
递归法
后序遍历
这个后序遍历的方法其实和二叉树的最大深度的差不多，需要注意的就是，根节点左右子树的特殊情况，当根节点的其中一个子树为空的时候，要保证程序选择了非空子树的最小高度
求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
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 && root.right != null) { return rightDepth + 1; //两个作用：挑选出右子树|加成根节点的高度 } if (root.right == null && root.left != null) { return leftDepth + 1; } // 然后在进行中间节点的处理 int rootMinDerth = 1 + Math.min(leftDepth,rightDepth); return rootMinDerth; } }
迭代法
层序遍历
如果你遍历到一个节点的左右子节点，那说明这个节点就是叶子节点，也就是碰到了最小深度了
class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } // 创建队列 Deque<Node> deque = new ArrayDeque<>(); // 将根节点添加到队列中 deque.offer(root); // 定义深度 int depth = 0; // 开始层序遍历 while (!deque.isEmpty()) { // 获取当前层数的节点个数 int len = deque.size(); // 弹出此层节点，添加对应的孩子节点 while (len-- > 0) { Node node = deque.poll(); for (Node child : node.children) { deque.offer(child); } } depth++; } return depth; } }
222.完全二叉树的节点个数
题目链接：力扣
思路
可以把完全二叉树当作普通二叉树进行节点计数，所有可以遍历二叉树的方式都是可以的
再就是根据完全二叉树的特性对二叉树的节点进行统计，一般的二叉树递归到节点为null就终止递归，完全二叉树除了这种情况还有就是可以递归到满二叉树的时候终止递归
完全二叉树的节点个数
递归法
使用完全二叉树的特性
这个方法是使用了完全二叉树的特性，递归到最后只会有两种情况：
情况一：是个满二叉树
情况二：最后一层叶子节点没有满
对于情况一，直接使用2^k -1 求出满二叉树的节点个数（k代表满二叉树的最大深度）
对于情况二，分别递归左右子树，递归到某一深度一定会有左孩子或者右孩子是满二叉树，然后按照情况一来处理，叶子节点也是满二叉树
class Solution { public int countNodes(TreeNode root) { // 如果遇到了空节点，递归终止，空节点的节点总数为0 if (root == null) { return 0; } // 如果遇到了满二叉树，递归终止，满二叉树的节点总数为2^n - 1; TreeNode left = root.left; TreeNode right = root.right; int leftdepth = 0; int rightdepth = 0; while (left != null) { left = left.left; leftdepth++; } while (right != null) { right = right.right; rightdepth++; } if (leftdepth == rightdepth) { // 在完全二叉树中，当节点外侧的深度相等的时候，那么这个节点代表的树就是满二叉树 return (2 << rightdepth) - 1; } int leftNum = countNodes(root.left); int rightNum = countNodes(root.right); return leftNum + rightNum + 1; } }
使用普通二叉树的方法
采用后序遍历的形式，不得不说递归虽然不太好理解，但是真的是优美呀
class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int leftNum = countNodes(root.left); int rightNum = countNodes(root.right); int num = leftNum + rightNum + 1; return num; } }
//精简版 class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } return countNodes(root.left) + countNodes(root.right) + 1; } }
迭代法
层序遍历：每出队一个元素就记录一次
class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } Deque<TreeNode> deque = new ArrayDeque<>(); deque.offer(root); int num = 0; while (!deque.isEmpty()) { int len = deque.size(); for (int i = 0; i < len; i++) { TreeNode node = deque.poll(); num++; if (node.left != null) { deque.offer(node.left); } if (node.right != null) { deque.offer(node.right); } } } return num; } }
