559.n叉树的最大深度
给定一个 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
问题分析：
同111题，利用递归，根节点的高度就是整个二叉树的深度。
-
class
Solution {
-
public
int
maxDepth
(Node root) {
-
if (root==
null)
return
0;
-
int dep=
0;
-
if (root.children!=
null){
-
for(Node child:root.children){
-
dep=Math.max(dep,maxDepth(child));
-
}
-
}
-
return dep+
1;
-
}
-
}
222.完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含1~
个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
问题分析：
递归法：
①遍历左右子树的外侧节点（内侧节点不用遍历，因为是满二叉树，内侧一定有节点）， 如果左右两侧的外侧节点数量相等，就是满二叉树，直接利用公式2^h-1，求出满二叉树的节点数量， 在返回给上一层节点，再+1。（一个节点也是满二叉树）
②精简版，按照普通二叉树来看。
方法一：利用满二叉树法
-
class
Solution {
-
public
int
countNodes
(TreeNode root) {
-
if (root==
null)
return
0;
-
TreeNode left=root.left;
-
TreeNode right=root.right;
-
int leftdep=
0,rightdep=
0;
//其实起始值应为1，但是按位操作，原因见下
-
while(left!=
null){
-
left=left.left;
-
leftdep++;
-
}
-
while (right!=
null){
-
right=right.right;
-
rightdep++;
-
}
-
if (leftdep ==rightdep){
-
return (
2<<leftdep)-
1;
-
//<<：左移： 2 <<= dep 相当于2 * 2^dep,此时多乘了个2，所以一开始初始化为0
-
}
-
return countNodes(root.left)+countNodes(root.right)+
1;
//注意递归
-
}
-
}
方法二：精简版
-
class
Solution {
-
public
int
countNodes
(TreeNode root) {
-
if (root==
null)
return
0;
-
-
return countNodes(root.left)+countNodes(root.right)+
1;
-
-
}
-
}
转载：https://blog.csdn.net/weixin_52767345/article/details/128677006
查看评论