递归方程式

主定理

主定理 (Master Theorem) 是求解递归方程式最有效的方法，其概述如下：

假设有递归方程式 \(T(n)=aT(\frac{n}{b})+f(n)\) ，其中 \(a, b\) 是常数，且 \(a\geq 1, b > 1\) ， \(f(n)\) 是渐近正函数。则：

若 \(\exists \varepsilon>0\) 使 \(f(n)=O(n^{log_b{a-\varepsilon}})\) ，则 \(T(n)=\Theta(n^{\log_ba})\)
若 \(f(n)=\Theta(n^{\log_ba})\) ，则 \(T(n)=\Theta(n^{\log_ba}\lg n)\)
若 \(\exists \varepsilon>0\) ，有 \(f(n)=\Omega(n^{\log_b{a+\varepsilon}})\) ，且对某个常数 \(c<1\) 和所有足够大的 \(n\) 有 \(af(\frac{n}{b})\leq cf(n)\) ，则 \(T(n)=\Theta(f(n))\)

递归

递归最重要的地方就是知道当前函数的功能，如果功能判断错误，就会导致做出无用工，还会导致 Bug

例如：

二叉树展开为链表^[1]

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

class Solution {
public:
   void flatten(TreeNode* root) {
      if(!root) return;
      flatten(root->left);
      flatten(root->right);
      auto tmp = root->right;
      root->right = root->left;
      root->left = nullptr;
      while(root->right) root = root->right;
      root->right = tmp;
   }
};

这里 flatten 的功能是：将左孩子展成链表、将右孩子展成链表、将右孩子拼接到左孩子上，将左孩子变成右孩子

如果判断出错，就会导致很多问题，最突出的就是边界错误：

class Solution {
public:
   void flatten(TreeNode* root) {
      if(!root) return;
      if(root->left&& root->left->left == nullptr && root->left->right == nullptr){
            // 若 root->left 是叶子节点
            root->left->right = root->right;
            root->right = root->left;
            root->left = nullptr;
            return;
      }
      flatten(root->left);
      flatten(root->right);
      auto head = root->left;
      if(!head) return;
      while(head->right){
            auto tmp = head->right;
            if(!tmp) break;
            head = head->right;
      }
      head->right = root->right;
      root->right = root->left;
      root->left = nullptr;
   }
};

之所以错误，就是因为做题时将 flatten 功能误认为是简单地将右孩子拼接到左孩子上，此代码在测试中会失败。