leetcode刷题详解五

关键点：先递归右子树

画一下就知道了，画一个四层的二叉树，然后右子树多画几个节点就知道为啥了

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){
           cout<<"1"<<endl;
           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;
    }

将左子树上的东西都放到右子树上去，递归的写，注意，只关注局部即可。

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;
}

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(vector<int>& nums) {
        int left = 0;
        int right = nums.size();
        return build_binary_tree(nums, left, right);
    }

    
    TreeNode* build_binary_tree(vector<int>& 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;
    }

代码思路还是跟654题一模一样，可以说，构造二叉树的题递归代码都差不多！

这道题的思路用一下图片即可说明：

详细思路可以看这里

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0){
            return nullptr;
        }
        return build_tree_instance(preorder, 0, preorder.size(), 
        inorder, 0, inorder.size());
    }
    TreeNode* build_tree_instance(vector<int>& preorder, int pre_left, int pre_right,
    vector<int>& 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_left+1, pre_left+left_count,
        inorder, in_left, index);
        root->right = build_tree_instance(preorder,pre_left+left_count+1, pre_right,
         inorder, index+1, in_right);
         return root;
    }

跟上一题思路一模一样

但是这道题第一次做困了很久，就是边界找不准，一直有问题，一定要好好想想。

主要是前序和后序数组的边界不好找，中序的两道题都一样。

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0){
            return nullptr;
        }
        return bulid_tree_instance(inorder, 0, inorder.size(),
        postorder, 0, postorder.size()); 
    }
    TreeNode* bulid_tree_instance(vector<int>& inorder, int in_left, int in_right,
    vector<int>& 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_left+left_count);
        root->right = bulid_tree_instance(inorder, index+1, in_right,
        postorder, post_left+left_count, post_right-1); //post_right -1 这个是最容易被忽视的，后序遍历要看最后一个值
        return root;
    }

这道题的思想还是一个：对于树的某一个节点，清楚他要干啥！

所以这道题有两步：①以我自己为根的子树长什么样子。 ②以其他节点为根的子树的样子

以某一个节点为根的子树的样子，很明显就是后序遍历

接着序列化原先的二叉树，对比一下就行

文章参考链接

map<string,int> map_tree;
    vector<TreeNode*> vec_tree;
    vector<TreeNode*> 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。

  1. set就是数学上所说的元素的集合，可以理解为键和值完全相等的关联式容器。set会根据各个元素值的大小进行生序排序，底层使用红黑树来实现。值不能重复，由insert保证。
  2. map是由键和值两部分组成的关联式容器。键必须唯一，因此如果遇到有相同键的情况，可以使用[]运算符让值++，比如map[str]++。根据键map会进行生序排序。insert保证了键的唯一性。底层用红黑树实现。
  3. multiset。顾名思义，键（值）可以重复的关联式容器。底层用红黑树实现。
  4. multimap。键可以重复的关联式容器，其他与map都一样。
  5. unordered_set。底层是哈希表，占用空间较多，查找是常数时间。无自动排序功能。
  6. unordered_map。底层是哈希表，占用空间较多，查找是常数时间。无自动排序功能。

• 思路：本质上就是节点间信息的交流。那么二叉树有三种信息交流的方式，前序，中序和后序。

  由于我们可以分析，返回最小的摄像头数量，那么我们肯定尽量不在子节点装摄像头，而是在父节点装。因此从子节点往父节点传递信息的方式是后序遍历，我们可以用后序遍历的形式做这道题。

  很自然，每个节点肯定有三种该状态啦：

  • 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;
      }