做仿牌网站被封,动态公司网站设计,铜川网站建设电话,装饰公司在哪个网站上接活117. 填充每个节点的下一个右侧节点指针 II 关键点#xff1a;先递归右子树 画一下就知道了#xff0c;画一个四层的二叉树#xff0c;然后右子树多画几个节点就知道为啥了 Node* connect(Node* root) {if(!root || (!root-left !root-right)){return ro…117. 填充每个节点的下一个右侧节点指针 II 关键点先递归右子树 画一下就知道了画一个四层的二叉树然后右子树多画几个节点就知道为啥了 Node* connect(Node* root) {if(!root || (!root-left !root-right)){return root;}if(root-left root-right){root-left-next root-right;root-right-next get_next_node(root);}if(!root-right){cout1endl;root-left-next get_next_node(root);}if(!root-left){root-right-next get_next_node(root);}connect(root-right);connect(root-left);return root;}Node* get_next_node(Node* root){while(root-next){if(root-next-left){return root-next-left;}else if(root-next-right){return root-next-right;}root root-next;}return nullptr;}114. 二叉树展开为链表 将左子树上的东西都放到右子树上去递归的写注意只关注局部即可。 void flatten(TreeNode* root) {if(!root ){return ;}flatten(root-left);flatten(root-right);//最后处理根节点TreeNode* tmp_right root-right;root-right root-left;root-left nullptr;TreeNode* tmp root;while(tmp-right){tmp tmp-right;}tmp-right tmp_right;
}654. 最大二叉树 TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) { // 找到数组中的最大值 TreeNode root new TreeNode(6); // 递归调用构造左右子树 root.left constructMaximumBinaryTree([3,2,1]); root.right constructMaximumBinaryTree([0,5]); return root;}上面代码就是本体的答题思路。 对于构造二叉树的问题根节点要做的就是把想办法把自己构造出来。 TreeNode* constructMaximumBinaryTree(vectorint nums) {int left 0;int right nums.size();return build_binary_tree(nums, left, right);}TreeNode* build_binary_tree(vectorint nums, int left, int right){//递归结束条件if(left right){return nullptr;}int max INT_MIN;int index -1;for(int i left;i right;i){if(max nums[i]){max nums[i];index i;}}TreeNode* root new TreeNode(max);root-left build_binary_tree(nums, left, index);root-right build_binary_tree(nums, index 1, right);return root;}⭕️105. 从前序与中序遍历序列构造二叉树★面试常考 代码思路还是跟654题一模一样可以说构造二叉树的题递归代码都差不多 这道题的思路用一下图片即可说明 详细思路可以看这里 TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.size() 0){return nullptr;}return build_tree_instance(preorder, 0, preorder.size(), inorder, 0, inorder.size());}TreeNode* build_tree_instance(vectorint preorder, int pre_left, int pre_right,vectorint inorder, int in_left, int in_right){if(in_left in_right){return nullptr;}int left_count 0;int index -1;int root_value preorder[pre_left];for(int i in_left;i in_right; i){if(root_value inorder[i]){index i;break;}}left_count index - in_left;TreeNode* root new TreeNode(root_value);root-left build_tree_instance(preorder,pre_left1, pre_leftleft_count,inorder, in_left, index);root-right build_tree_instance(preorder,pre_leftleft_count1, pre_right,inorder, index1, in_right);return root;}⭕️106. 从中序与后序遍历序列构造二叉树 跟上一题思路一模一样 但是这道题第一次做困了很久就是边界找不准一直有问题一定要好好想想。 主要是前序和后序数组的边界不好找中序的两道题都一样。 TreeNode* buildTree(vectorint inorder, vectorint postorder) {if(inorder.size() 0){return nullptr;}return bulid_tree_instance(inorder, 0, inorder.size(),postorder, 0, postorder.size()); }TreeNode* bulid_tree_instance(vectorint inorder, int in_left, int in_right,vectorint postorder, int post_left, int post_right){if(in_left in_right){return nullptr;}int index 0;int left_count 0;int root_val postorder[post_right-1];for(int i in_left;i in_right; i){if(root_val inorder[i]){index i;break;}}left_count index - in_left;TreeNode* root new TreeNode(root_val);root-left bulid_tree_instance(inorder,in_left, index,postorder,post_left, post_leftleft_count);root-right bulid_tree_instance(inorder, index1, in_right,postorder, post_leftleft_count, post_right-1); //post_right -1 这个是最容易被忽视的后序遍历要看最后一个值return root;}652. 寻找重复的子树 这道题的思想还是一个对于树的某一个节点清楚他要干啥 所以这道题有两步①以我自己为根的子树长什么样子。 ②以其他节点为根的子树的样子 以某一个节点为根的子树的样子很明显就是后序遍历 接着序列化原先的二叉树对比一下就行 文章参考链接 mapstring,int map_tree;vectorTreeNode* vec_tree;vectorTreeNode* findDuplicateSubtrees(TreeNode* root) {sqe_tree(root);return vec_tree;}string sqe_tree(TreeNode* root){if(!root){return #;}string left sqe_tree(root-left);string right sqe_tree(root-right);string str_tree left , right , to_string(root-val);if(map_tree[str_tree] 1){vec_tree.push_back(root);}//重要map_tree[str_tree];return str_tree;}这道题总结一下有以下两个点。本题涉及的数据结构知识本题的细节。 本题的细节 这道题耗费我较多时间。有几个需要注意的点。 二叉树序列化的方法需要写一个辅助函数完成辅助函数的返回值用string这个需要好好记住。最开始存储序列化后的字符串用的是set但我发现一个巨大的问题。即如果有set中重复的被找到则放到vector中这本来没什么问题但是注意这里面有个坑即只要重复就放到vector中。这是you逻辑问题的因为如果一个字符串重复了5次vector中应该只有一个根节点但是代码会放4次相同的根节点这样vector中会出现重复这是会出错的。所以用map方便。 涉及的数据结构 stl的关联式容器中有两个大类set和map。由这两个基本关联式容器衍生出来很多例如multimap、multiset、unordered_map、unordered_set。 set就是数学上所说的元素的集合可以理解为键和值完全相等的关联式容器。set会根据各个元素值的大小进行生序排序底层使用红黑树来实现。值不能重复由insert保证。map是由键和值两部分组成的关联式容器。键必须唯一因此如果遇到有相同键的情况可以使用[]运算符让值比如map[str]。根据键map会进行生序排序。insert保证了键的唯一性。底层用红黑树实现。multiset。顾名思义键值可以重复的关联式容器。底层用红黑树实现。multimap。键可以重复的关联式容器其他与map都一样。unordered_set。底层是哈希表占用空间较多查找是常数时间。无自动排序功能。unordered_map。底层是哈希表占用空间较多查找是常数时间。无自动排序功能。
968. 监控二叉树 思路本质上就是节点间信息的交流。那么二叉树有三种信息交流的方式前序中序和后序。 由于我们可以分析返回最小的摄像头数量那么我们肯定尽量不在子节点装摄像头而是在父节点装。因此从子节点往父节点传递信息的方式是后序遍历我们可以用后序遍历的形式做这道题。 很自然每个节点肯定有三种该状态啦 0表示没有被监控1表示该节点有摄像头2表示被监控到了 然后我们就按照后序遍历依次传递消息。 本质上是贪心因为如果子节点被覆盖了那么当前父节点就不要设置监视器这是一条隐形规则。 代码 class Solution {
public:int result;int minCameraCover(TreeNode* root) {result 0;if(bianli(root) 0){result;}return result;}int bianli(TreeNode* root){if(root nullptr){return 2;}int left bianli(root-left);int right bianli(root-right);//逻辑部分// 0表示没有被监控// 1表示该节点有摄像头// 2表示被监控到了//①左右节点都被监控了。因为是自下而上已经被监控了其父节点就不用摄像头了父节点就是没被监控if(left 2 right 2){return 0;}//②左右节点至少有一个没被监控。说明父节点要放摄像头if(left 0 || right 0){result;return 1;}//③左右节点至少有一个摄像头那么父节点会被监控到if(left 1 || right 1){return 2;}return -1;}
