力扣刷题(DAY09-DAY11)

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