Day09
0958. 二叉树的完全性检验
知识点：完全二叉树：在一棵完全二叉树中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第
h层）中可以包含1到个节点，
当最后一层全部都满（
题目大意：给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。
思路：尝试用层次遍历解决，如果存在上一个节点出队没有左孩子，但有右孩子，就是flase；
或者本节点都没有，但下一个有。可以设置bool will来判断 再深入思考一下，在遍历到当前节点的时候 ，前面如果已经出现过空节点，那他一定不是完全二叉树。
于是：层次遍历二叉树，无论节点是否存在，都放入队列中，当出现空节点的时候标记一下；继续遍历，如果后面还有结点，说明不是完全二叉树
其实也可以说完全二叉树，层次遍历到最后一个节点时一定不会出现空节点
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
// 层次遍历
bool will = 0;
queue<TreeNode*> q;
TreeNode* visited;
q.push(root);
while (!q.empty()) {
visited = q.front();
q.pop();
if (visited == NULL) {
will = 1; // 空节点
} else {
if (will) // 前面有一个空
return false;
q.push(visited->left);
q.push(visited->right);
}
}
return true;
}
};这里强调说明一下：
visited = q.front(); 一定要放在前面写0543. 二叉树的直径
题目要求：
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。
思路：长度最长的路线应该是从左边的最高高度到右边的最高高度；根据边计算一下，应该是左hight+右hight-1---》左子树高度+柚子树高度;
好好好，按着这样写下去，出现这个情况了……
树大概张这个样子
重新想思路：犯错原因只考虑了焦点在根节点的情况，
于是升级版：递归地计算每个节点的左子树和右子树的深度，并在遍历的过程中更新最大直径，最终得到整棵树的直径。
max_len=max(height(vistied->left)+height(vistied->right),max_len) ;
//visited 每个结点，用中序遍历一下吧;于是代码就有了：
class Solution {
public:
int max_len=0;
int height(TreeNode* root){//求高度
if(!root) return 0;
return max(height(root->left),height(root->right))+1;
}
void inorder(TreeNode* root){//每个结点，用中序遍历一下吧;
if(!root) return;
inorder(root->left);
max_len=max(height(root->left)+height(root->right),max_len) ;
inorder(root->right);
}
int diameterOfBinaryTree(TreeNode* root) {
if(!root) return 0;
inorder(root);
return max_len;
}
};思路有了，不放在优化一下
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int maxDiameter = 0;
maxDepth(root, maxDiameter);
return maxDiameter;
}
int maxDepth(TreeNode* node, int& maxDiameter) {
if (node == nullptr) {
return 0;
}
int leftDepth = maxDepth(node->left, maxDiameter);
int rightDepth = maxDepth(node->right, maxDiameter);
maxDiameter = max(maxDiameter, leftDepth + rightDepth);
return 1 + max(leftDepth, rightDepth);
}
};
0662. 二叉树最大宽度
题目大意：
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
想到一种这个情况，测试结果为4；
思路：求层的宽度，当然是层次遍历bfs啦，那怎么保证左孩子不存在，右孩子还能存进去的？
还记得树的顺序存储么？用这个就好。left_index=双亲*2；right_index=双亲*2+1；
这样我们层次遍历是，可以建立二维队列
queue<pair<TreeNode*, unsigned long long>> q;为什么unsigned longlong 呢？ 因为题目所给的数据范围是3000个节点，如果没层一个节点且都靠右排列，那么会有1000多层的树。 这样导致在树底部的节点编号为2的一千多次方。而这个范围在多数语言中都是没办法正常处理的。
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int max_width = 0;
queue<pair<TreeNode*, unsigned long long>> q;
q.push({root, 1});
while (!q.empty()) {
int size = q.size();
unsigned long long leftmost = q.front().second;
unsigned long long rightmost = leftmost;
for (int i = 0; i < size; i++) {
auto [node, index] = q.front();
q.pop();
if (i == 0) {
leftmost = index;
}
if (i == size - 1) {
rightmost = index;
}
if (node->left) {
q.push({node->left, 2 * index});
}
if (node->right) {
q.push({node->right, 2 * index + 1});
}
}
max_width = max(static_cast<int>(rightmost - leftmost + 1), max_width);
}
return max_width;
}
};
好了，今天就到这里 over
