104.二叉树的最大深度
题目链接 : 104. 二叉树的最大深度 - 力扣（LeetCode）
题目
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
思路
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
- 二叉树节点的深度：指从 根节点 到 该节点 的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从 该节点 到 叶子节点 的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度。所以本题可以层序遍历二叉树，每遍历一层深度就加一。
代码
递归法（后序）
1 class solution {
2 /**
3 * 递归法(后序)
4 */
5 public int maxDepth(TreeNode root) {
6 if (root == null) {
7 return 0;
8 }
9 int leftDepth = maxDepth(root.left);
10 int rightDepth = maxDepth(root.right);
11 return Math.max(leftDepth, rightDepth) + 1;
12 }
13 }
递归法(前序)
1 class Solution {
2 /**
3 * 递归法(求深度法)
4 */
5 //定义最大深度
6 int maxnum = 0;
7
8 public int maxDepth(TreeNode root) {
9 ans(root,0);
10 return maxnum;
11 }
12
13 //递归求解最大深度
14 void ans(TreeNode tr,int tmp){
15 if(tr==null) return;
16 tmp++;
17 maxnum = maxnum<tmp?tmp:maxnum;
18 ans(tr.left,tmp);
19 ans(tr.right,tmp);
20 tmp--;
21 }
22 }
迭代法
1 class solution {
2 /**
3 * 迭代法，使用层序遍历
4 */
5 public int maxDepth(TreeNode root) {
6 if(root == null) {
7 return 0;
8 }
9 Deque<TreeNode> deque = new LinkedList<>();
10 deque.offer(root);
11 int depth = 0;
12 while (!deque.isEmpty()) {
13 int size = deque.size();
14 depth++;
15 for (int i = 0; i < size; i++) {
16 TreeNode node = deque.poll();
17 if (node.left != null) {
18 deque.offer(node.left);
19 }
20 if (node.right != null) {
21 deque.offer(node.right);
22 }
23 }
24 }
25 return depth;
26 }
27 }
559.n叉树的最大深度
题目链接 : 559. N 叉树的最大深度 - 力扣（LeetCode）
题目
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5
思路
同上面题同理。
代码
1 class Solution {
2 /*递归法，后序遍历求root节点的高度*/
3 public int maxDepth(Node root) {
4 if (root == null) return 0;
5
6 int depth = 0;
7 if (root.children != null){
8 for (Node child : root.children){
9 depth = Math.max(depth, maxDepth(child));
10 }
11 }
12
13 return depth + 1; //中节点
14 }
15 }
1 class solution {
2 /**
3 * 迭代法，使用层序遍历
4 */
5 public int maxDepth(Node root) {
6 if (root == null) return 0;
7 int depth = 0;
8 Queue<Node> que = new LinkedList<>();
9 que.offer(root);
10 while (!que.isEmpty())
11 {
12 depth ++;
13 int len = que.size();
14 while (len > 0)
15 {
16 Node node = que.poll();
17 for (int i = 0; i < node.children.size(); i++)
18 if (node.children.get(i) != null)
19 que.offer(node.children.get(i));
20 len--;
21 }
22 }
23 return depth;
24 }
25 }
111.二叉树的最小深度
题目链接 : 111. 二叉树的最小深度 - 力扣（LeetCode）
题目
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
思路
本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。
注意：题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
代码
1 class Solution {
2 /**
3 * 递归法，相比求MaxDepth要复杂点
4 * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
5 */
6 public int minDepth(TreeNode root) {
7 if (root == null) {
8 return 0;
9 }
10 int leftDepth = minDepth(root.left);
11 int rightDepth = minDepth(root.right);
12 if (root.left == null) {
13 return rightDepth + 1;
14 }
15 if (root.right == null) {
16 return leftDepth + 1;
17 }
18 // 左右结点都不为null
19 return Math.min(leftDepth, rightDepth) + 1;
20 }
21 }
1 class Solution {
2 /**
3 * 迭代法，层序遍历
4 */
5 public int minDepth(TreeNode root) {
6 if (root == null) {
7 return 0;
8 }
9 Deque<TreeNode> deque = new LinkedList<>();
10 deque.offer(root);
11 int depth = 0;
12 while (!deque.isEmpty()) {
13 int size = deque.size();
14 depth++;
15 for (int i = 0; i < size; i++) {
16 TreeNode poll = deque.poll();
17 if (poll.left == null && poll.right == null) {
18 // 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
19 return depth;
20 }
21 if (poll.left != null) {
22 deque.offer(poll.left);
23 }
24 if (poll.right != null) {
25 deque.offer(poll.right);
26 }
27 }
28 }
29 return depth;
30 }
31 }
222.完全二叉树的节点个数
题目链接 : 222. 完全二叉树的节点个数 - 力扣（LeetCode）
题目
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
思路
迭代法的思路是层序遍历二叉树，每遇到一个节点就计数加一。
前序遍历递归法的思路是返回左子树和右子树所有节点个数并且加上当前节点的个数(1)。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树。
代码
1 class Solution {
2 // 通用递归解法
3 public int countNodes(TreeNode root) {
4 if(root == null) {
5 return 0;
6 }
7 return countNodes(root.left) + countNodes(root.right) + 1;
8 }
9 }
1 class Solution {
2 /**
3 * 针对完全二叉树的解法
4 *
5 * 满二叉树的结点数为：2^depth - 1
6 */
7 public int countNodes(TreeNode root) {
8 if (root == null) return 0;
9 TreeNode left = root.left;
10 TreeNode right = root.right;
11 int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
12 while (left != null) { // 求左子树深度
13 left = left.left;
14 leftDepth++;
15 }
16 while (right != null) { // 求右子树深度
17 right = right.right;
18 rightDepth++;
19 }
20 if (leftDepth == rightDepth) {
21 return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
22 }
23 return countNodes(root.left) + countNodes(root.right) + 1;
24 }
25 }
1 class Solution {
2 // 迭代法
3 public int countNodes(TreeNode root) {
4 if (root == null) return 0;
5 Queue<TreeNode> queue = new LinkedList<>();
6 queue.offer(root);
7 int result = 0;
8 while (!queue.isEmpty()) {
9 int size = queue.size();
10 while (size -- > 0) {
11 TreeNode cur = queue.poll();
12 result++;
13 if (cur.left != null) queue.offer(cur.left);
14 if (cur.right != null) queue.offer(cur.right);
15 }
16 }
17 return result;
18 }
19 }
标签：int,随想录,二叉树,深度,null,root,节点 From： https://www.cnblogs.com/xpp3/p/17136071.html