今日内容：
● 104.二叉树的最大深度 559.n叉树的最大深度
● 111.二叉树的最小深度
● 222.完全二叉树的节点个数
迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。
详细布置
104.二叉树的最大深度 （优先掌握递归）
什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。
大家 要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。
题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public int maxDepth(TreeNode node) {
if (node == null) {
return 0;
}
int leftDepth = maxDepth(node.left);
int rightDepth = maxDepth(node.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
class Solution {
public int maxDepth(TreeNode node) {
if (node == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(node);
int depth = 0;
while (!deque.isEmpty()){
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node1 = deque.poll();
if (node1.left != null){
deque.offer(node1.left);
}
if (node1.right != null){
deque.offer(node1.right);
}
}
}
return depth;
}
}
111.二叉树的最小深度 （优先掌握递归）
先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html
class Solution {
/**
* 递归法，相比求MaxDepth要复杂点
* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
*/
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;
}
}
222.完全二叉树的节点个数（优先掌握递归）
需要了解，普通二叉树 怎么求，完全二叉树又怎么求
题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html
class Solution {
// 迭代法
public int countNodes(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode cur = queue.poll();
result++;
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return result;
}
}
class Solution {
// 通用递归解法
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
class Solution {
/**
* 针对完全二叉树的解法
*
* 满二叉树的结点数为：2^depth - 1
*/
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
// 开始根据做深度和有深度是否相同来判断该子树是不是满二叉树
if (leftDepth == rightDepth) {// 左子树是满二叉树
// 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
// 注意(1<<) 相当于1^h，返回满足满二叉树的子树节点数量
return (1 << leftDepth) + countNodes(root.right);
} else {// 右子树是满二叉树
// 注意(<<) 相当于2^h，返回满足满二叉树的子树节点数量
return (1 << rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
}
<<左移运算，>>右移运算，还有不带符号的位移运算 >>>.
左移的运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。
可以看到这个二进制串在内存中整体向左移动了两位，那么最左边的两位就跑到内存单元的外面去了，这两位数字将会被舍弃，右边空出的两位用0补齐。
左移运算有乘以2的N次方的效果。一个数向左移动1位，就相当于乘以2的1次方，移动两位就相当于乘以2的2次方，也就是乘以4。位移操作在实际运算时远远快于乘法操作，所以在某些对运算速度要求非常高的场合，可以考虑用左移代替乘以2的N次方的乘法操作。但是需要提醒大家注意三个细节：
首先：位移操作同取反操作一样，并不能改变变量本身的值，所能改变的仅是存储在操作数栈中那个数据的值。
其次：当位移的位数很多时，导致最左边的符号位发生变化，就不再具有乘以2的N次方的效果了。比如十进制的5转换为补码形式是：前面29个0最后3位是101，如果移动29位，那么最前面的符号位就变成了1，此时运算的结果就成为了一个负数，不再是5乘以2的29次方的乘法结果。
最后：对于byte/short/int三种类型的数据，Java语言最多支持31位的位移运算。如果位移数超过31，则虚拟机会对位移数按连续减去32，直到得到一个小于32并且大于等于0的数，然后以这个数作为最终的位移数。例如对int型变量进行位移97位的操作，虚拟机会首先对97连续减去3个32，最终得到数字1，实际进行位移运算时只对变量位移1位。而对于long类型的数据而言，最多支持63位的位移运算，如果位移数超过63，则连续减去64，以最终得到的小于64并且大于等于0的数作为位移数。
右移运算分为两种，分别是带符号右移和无符号右移。首先我们来说说带符号右移运算符。带符号右移运算符的写法是”>>“，与左移运算符的方向恰好相反。所谓带符号右移就是指当二进制串向右边移动以后，左边空出的位用”符号位上的数字”填充，说的更直白一点，如果是正数，二进制串右移的时候用0来填充左边的空位，而对于负数而言，右移的时候用1来填充左边的空位。
>>运算规则：按二进制形式把所有的数字向右移动对应的位数，低位移出（舍弃），高位的空位补符号位，即正数补零，负数补1.
带符号右移操作在二进制串移动之后左边空位是怎样被填充的。之前强调过，左移N位的操作具有乘以2的N次方的效果，其实带符号右移也具有”类似”除以2的N次方的效果。请注意，这里说的是“类似”除以2的N次方的效果，为什么要加上“类似”两个字呢？就是因为对于正数而言，带符号右移之后产生的数字确实等于除以2的N次方，比如说我们把N的值设为3，对于正15，带符号右移3位的结果是1，这个结果与“15除以2的3次方”的结果是相同的。
但是对于负数而言，带符号右移的效果分为两种情况，我们分别来讨论。
如果这个负数是“2的N次方”的整数倍，那么带符号右移N位的效果也等于除以2的N次方。举个例子：我们还是把N的值设为3，如果对于“-16”来说，它是“2的3次方”的整数倍，那么带符号右移3位的结果是-2，这个结果相当于“-16除以2的3次方”。
而如果这个负数不是“2的N次方”的整数倍，那么右移N位之后，是在除以2的N次方的结果之上还要减去1。比如，对于-15来说，它不是“2的3次方”的整数倍，那么带符号右移3位的结果是-2，这个运算结果其实就是“-15被2的3次方整除再减去1”。小伙伴们也可以用其他负整数来验证一下这个结论。因为并非每个负整数带符号右移的结果都等于除以“2的N次方”，所以我们才在文中添加了“类似”这两个字。
带符号右移的操作可以保证移动之前和移动之后数字的正负属性不变，原来是正数，不管移动多少位，移动之后还是正数，原来是负数，移动之后还是负数。另外，我们还可以继续深挖一下这个特性，从而得到一个结论：对于任何一个byte、short或者int类型的数据而言，带符号右移31位之后，得到的必然是0或者是-1。对于long类型的数据而言，带符号右移63位之后，得到的也必然是0或者是-1。能够得出这个结论的依据也很简单，就是因为对于byte、short和int类型的变量而言，如果是正数，带符号右移31位之后产生的二进制串必然全部是0，转换成对应的十进制数就是0；而对于负数而言，带符号右移31位之后产生的二进制串必然全部是1，转换成十进制数就是-1。对于long类型的数据，带符号右移63位也具有相同效果。
无符号右移运算符
前文已说过：右移运算分为两种，分别是带符号右移和无符号右移。现在再来讲解无符号右移。无符号右移运算符的写法是”>>>”，比带符号右移多了一个”>”。带符号右移的运算规则与无符号右移的运算规则差别就在于：无符号右移在二进制串移动之后，空位由0来补充，与符号位是0还是1毫无关系，如下图：
对于正数而言，无符号右移和带符号右移没有什么区别，而对于负数而言，经过无符号右移会产生一个正数，因为最左边的符号位被0填充了。
>>>运算规则：按二进制形式把所有的数字向右移动对应的位数，低位移出（舍弃），高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同
标签：右移,带符号,随想录,int,二叉树,深度,次方,root From： https://www.cnblogs.com/gaoyuan2lty/p/17048279.html