leetcode_tips

发表于 | 分类于

  • 寻找一棵Tree的每层中的一个特殊值时，两种方法：广度搜索、深度搜索。

    1. 广度搜索模板：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      queue<int> que;
      que.push(root);
      while(que.size()>0){
          int num=que.size();//当前que中只存储了一层的节点
          for(int i=0;i<num;i++){//一次将一层中的节点遍历
              TreeNode* cur_row=que.front();
              que.pop();
              //do something to get the value of this level here
              if(root->left!=NULL)
                  que.push(root->left);
              if(root->right!=NULL)
                  que.push(root->right);
          }
      }

    2. 深度搜索模板，例如找每层最右边的节点值：

      1
      2
      3
      4
      5
      6
      7
      8
      void dfs(TreeNode* root,int level,vector<int>& result){
          if(!root) return;
          //当前level还没找到最右边的值，将当前值作为该level的最右边值
          if(result.size()<level) result.push_back(root->val);
          //接着找下一层最右边的值
          dfs(root->right,level+1,result);
          dfs(root->left,leve+1,result);
      }

  • 四平方和定理

    四平方和定理说明每个正整数均可表示为4个整数的平方和。除了满足以下这个公式的数以外的任何数都可以由3个平方数组成：