########################################
递归方程式
########################################

主定理
****************************************

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

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

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

递归
****************************************

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

例如：

二叉树展开为链表 [#bin]_

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

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

.. code-block:: cpp

   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 的功能是：将左孩子展成链表、将右孩子展成链表、将右孩子拼接到左孩子上，将左孩子变成右孩子

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

.. code-block:: cpp

   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 功能误认为是简单地将右孩子拼接到左孩子上，此代码在测试中会失败。


.. [#bin] `二叉树展开为链表 - 力扣 <https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/>`_