网站开发能干什么,重庆电子工程学院,莱芜雪野湖地图,才做的网站怎么搜不到Day09
0958. 二叉树的完全性检验 知识点#xff1a;完全二叉树#xff1a;在一棵完全二叉树中#xff0c;除了最后一层外#xff0c;所有层都被完全填满#xff0c;并且最后一层中的所有节点都尽可能靠左。最后一层#xff08;第 h 层#xff09;中可以包含 1 到 个节点…
Day09
0958. 二叉树的完全性检验 知识点完全二叉树在一棵完全二叉树中除了最后一层外所有层都被完全填满并且最后一层中的所有节点都尽可能靠左。最后一层第 h 层中可以包含 1 到 个节点 当最后一层全部都满 个节点的时候就称为满二叉树。 题目大意给你一棵二叉树的根节点 root 请你判断这棵树是否是一棵 完全二叉树 。
思路尝试用层次遍历解决如果存在上一个节点出队没有左孩子但有右孩子就是flase
或者本节点都没有但下一个有。可以设置bool will来判断 再深入思考一下在遍历到当前节点的时候 前面如果已经出现过空节点那他一定不是完全二叉树。
于是层次遍历二叉树无论节点是否存在都放入队列中当出现空节点的时候标记一下继续遍历如果后面还有结点说明不是完全二叉树 其实也可以说完全二叉树层次遍历到最后一个节点时一定不会出现空节点 class Solution {
public:bool isCompleteTree(TreeNode* root) {// 层次遍历bool will 0;queueTreeNode* 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_lenmax(height(vistied-left)height(vistied-right),max_len) ;
//visited 每个结点用中序遍历一下吧;
于是代码就有了 class Solution {
public:int max_len0;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_lenmax(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双亲*2right_index双亲*21
这样我们层次遍历是可以建立二维队列
queuepairTreeNode*, unsigned long long q;
为什么unsigned longlong 呢 因为题目所给的数据范围是3000个节点如果没层一个节点且都靠右排列那么会有1000多层的树。 这样导致在树底部的节点编号为2的一千多次方。而这个范围在多数语言中都是没办法正常处理的。
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {if (!root) return 0;int max_width 0;queuepairTreeNode*, 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_castint(rightmost - leftmost 1), max_width);}return max_width;}
};好了今天就到这里 over
