package LeetCode.Treepart03; /** * 222. 完全二叉树的节点个数 * 给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。 * 完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外, * 其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。 * 若最底层为第 h 层,则该层包含 1~2h个节点。 * */ public class CountCompleteTreeNodes_222 { // 通用递归解法 public int countNodes(TreeNode root) { if(root == null) { return 0; } return countNodes(root.left) + countNodes(root.right) + 1; } }
package LeetCode.Treepart03; /** * 104. 二叉树的最大深度 * 给定一个二叉树,找出其最大深度。 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 * 说明:叶子节点是指没有子节点的节点。 * 示例: * 给定二叉树 [3,9,20,null,null,15,7], * */ public class MaximumDepthofBinaryTree_104 { /** * 递归法 */ 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; } }
package LeetCode.Treepart03; /** * 559. N 叉树的最大深度 * 给定一个 N 叉树,找到其最大深度。 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 * N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。 * */ //public class MaximumDepthOfNTree_559 { // /*递归法,后序遍历求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; //中节点 // } //}
package LeetCode.Treepart03; /** * 111. 二叉树的最小深度 * 给定一个二叉树,找出其最小深度。 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 * 说明:叶子节点是指没有子节点的节点。 * */ public class MinimumDepthofBinaryTree_111 { 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; } }