回溯

二叉树的路径
LC257 二叉树的所有路径
LC112 路径总和
LC113 路径总和II
LC437 路径总和III
LC129 根到叶子组成的数字

组合
LC77 组合
LC40 组合总数II

简单回溯
LC93 复原IP地址
LC17 电话号码的字母组合
LC22 括号生成

困难回溯
LC10 正则表达式匹配
LC44 通配符匹配
LC79 单词搜索
[LC894 所有可能的满二叉树]

回溯是深度优先搜索决策树的过程。回溯的基本组件：

• 选择列表：当前可以选择的选项列表，可能因为当前路径而有所改变。因为对于当前路径而言，有些选择可能不合法。
• 当前路径：记录当前已经作出的选择的列表。
• 结束条件：判断当前路径是否是结果的函数。
• 结果集合：记录所有合法结果的集合。

  res = []
  path = []
  backtrack(path, decision_list)
  
      if (isResult(path))
          res.push_back(path)
          return
  
      for decision : decision_list
          if(!isValid(path, decision))
              continue
          path.push_back(decision)
          backtrack(path, decision_list)
          path.pop_back

---

二叉树的路径

二叉树除了根节点以外，每个节点都只有双亲节点。因此从根节点到任意节点都只有一条路径。从任意节点到根结节点也只有一条路径。这类题目的思路基本都是回溯。

二叉树的所有路径

LC257 二叉树的所有路径

思路：

• 对二叉树进行回溯
• 回溯结束条件为当前节点为叶子节点。
• 麻烦的地方可能在于"->"的放置。所有节点都要将自己的节点值root->val加入到path中，但叶子节点不需要加"->"，而且叶子节点需要将path放入结果集合里。而非叶子节点需要加"->"。此外，不同长度的数字，向path里放入的长度也不同。这导致了回溯时path需要删掉几个字符造成了不一致。所以我们需要记录一下我们往path里加了几个字符。
  code

  class Solution {
  private:
      string path;
      vector<string> paths;
  public:
      vector<string> binaryTreePaths(TreeNode* root) {
          backtrack(root);
          return paths;
      }
  
      void backtrack(TreeNode* root)
      {
          if(!root) return;
          // construct a string to update
          auto str = to_string(root->val);
          path += str;
          auto update_num = str.size();
          // if it is a leaf node, we dont want a dangling tail '->'
          if(!root->left && !root->right)
          {
              paths.push_back(path);
          }
          else
          {
              path += "->";
              update_num += 2;
  
              backtrack(root->left);
              backtrack(root->right);            
          }
          // resume its state
          path.erase(path.end() - update_num, path.end());
      }
  };

路径和

LC112 路径总和

题目要求判断二叉树中是否存在一条从根节点到叶子节点，和为指定值的一条路径。

• 回溯过程中记录当前路径上的和。
• 结束条件为当前节点是叶子节点，且当前路径和为指定的值。

code

class Solution {
private:
    int pathsum;
public:
    bool hasPathSum(TreeNode* root, int sum) {
        pathsum = sum;
        return hasPathSum_(root, 0);
    }

    bool hasPathSum_(TreeNode* root, int sum) {

        if(!root)
        {
            return false;
        }

        sum += root->val;
       
        // if root is a leaf node
        if(!root->left && !root->right)
        {
            
            // check the path sum
            if(sum == pathsum)
            {
                
                return true;
            }
            return false;
        }

        return hasPathSum_(root->left, sum) || hasPathSum_(root->right, sum);
    }
};

优化：设置sum初始值为目标值，并不断的向下减去当前节点的值。

code

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        return path_sum(root, sum);
    }

    bool path_sum(TreeNode* root, int sum)
    {
      if(!root)
      {
        return false;
      }

      sum -= root->val;

      if(!root->left && !root->right)
      {
        return sum == 0;
      }

      return path_sum(root->left, sum) || path_sum(root->right, sum);
    }
};

---

LC113 路径总和II

题目要求找到二叉树中所有从根节点到叶子节点，和为指定值的一条路径。思路仍然和前一题一样：

• 回溯过程要记录当前路径 和 当前路径和（不然每次抵达叶子节点，都需求一次路径和）。
• 结束条件为当前节点是叶子节点，且当前路径和为指定的值。
  2020.6.20 code

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
  class Solution {
  private:
      vector<vector<int>> m_res = {};
      vector<int> m_path = {};
      int m_sum = 0;
      int m_target = 0;
  public:
      vector<vector<int>> pathSum(TreeNode* root, int sum) {
          m_target = sum;
          backtrace(root);
          return m_res;
      }
  
      void backtrace(TreeNode* root) noexcept
      {
          if(!root)
          {
              return;
          }
  
          m_path.push_back(root->val);
          m_sum += root->val;
  
          if(m_sum == m_target && (!root->left && !root->right) )
          {
              m_res.push_back(m_path);
          }
  
          backtrace(root->left);
          backtrace(root->right);
  
          m_path.pop_back();
          m_sum -= root->val;
      } 
  };

code

class Solution {
private:
    vector<vector<int>> paths;
    vector<int> path;
    int pathsum;
    int cursum;
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        pathsum = sum;
        cursum = 0;

        backtrack(root);
        return paths;
    }

    void backtrack(TreeNode* root)
    {
        if(!root)
        {
            return;
        }
        cursum += root->val;
        path.push_back(root->val);

        // it is a leaf node
        if(!root->left && !root->right)
        {
            if (cursum == pathsum)
            {
                paths.push_back(path);
            }
        }
        else
        {
            backtrack(root->left);
            backtrack(root->right);
        }

        cursum -= root->val;
        path.pop_back();
    }
};

---

LC129 根到叶子组成的数字

需要二叉树中所有的路径形成的数字的和。将双亲节点传来的数字乘10后加上本节点的数字即可。

code

class Solution {
private:
    int res;
public:
    int sumNumbers(TreeNode* root) {
        res = 0;
        backtrack(root, 0);
        return res;
    }

    void backtrack(TreeNode* root, int num)
    {
        if(!root) return;

        num = num * 10 + root->val;

        // leaf node
        if(!root->left && !root->right)
        {
            res += num;
        }
        else
        {
            backtrack(root->left, num);
            backtrack(root->right, num);
        }
    }
};

---

LC437 路径总和III

题目要求找到二叉树中所有和为指定值的一条路径。路径不一定从根节点出发，也不一定在叶子节点结束，但路径方向一定是向下的（即不能从某一点处折返）。

思路一：

• 对树的每一个节点都进行一次回溯
• 回溯的结束条件为路径和为指定值

code

class Solution {
private:
    int pathsum;
    int res;
public:
    int pathSum(TreeNode* root, int sum) {
        pathsum = sum;
        res = 0;
        pathSum_(root);
        return res;
    }

    void pathSum_(TreeNode* root)
    {
        if(!root) return;
        backtrack(root, 0);
        pathSum_(root->left);
        pathSum_(root->right);
    }

    void backtrack(TreeNode* root, int sum)
    {
        if(!root) return;
        sum += root->val;
        if(sum == pathsum) ++res;
        backtrack(root->left, sum);
        backtrack(root->right, sum);
    }
};

---

思路二：

• 二叉树中从根节点到任意节点都只有一条路径。
• 不要求起点，也不要求终点，考虑这是一个区间和问题。区间和问题的解决手段往往都是前缀和。
• 设pathsum为想要的区间和。cursum为根节点到当前节点的和。
• 回溯过程中，使用一个hashmap记录路径上的前缀和。hashmap的key为前缀和，hashmap的val为该前缀和的数量。
• 更新结果：在当前节点判断hashmap中是否有key的值等于cursum - pathsum。（因为区间和等于前缀和的差，即cursum - key == pathsum）有，则说明找到了val条和为sum的路径。
• 更新hashmap：
  • 如果当前节点不是叶子节点，检查hashmap中是否有key等于当前节点处前缀和的，如果有就给key对应的val加1。如果没有就创建这样的一个key，对应val为1。
  • 如果当前节点是叶子节点，就没必要再更新hashmap了，因为不会有从当前节点往下的递归调用了。

注意：
在当前节点除了判断是否有key == cursum - pathsum，还需要判断一下是否cursum == pathsum，这也是一个解。如果不想判断cursum == pathsum，也可以在hashmap中加入一个(0, 1)的key-value对。表示到根结点的区间和。

code

class Solution {
private:
    int pathsum;
    int res;
    unordered_map<int, int> prefixSum;
public:
    int pathSum(TreeNode* root, int sum) {
        pathsum = sum;
        res = 0;
        backtrack(root, 0);
        return res;
    }

    void backtrack(TreeNode* root, int sum)
    {
        if(!root) return;
    
        sum += root->val;

        // this is also a possible solution, do not miss it
        if(sum == pathsum)
        {
            ++res;
        }

        if(prefixSum.count(sum - pathsum))
        {
            res += prefixSum[sum - pathsum];
        }

        ++prefixSum[sum];

        backtrack(root->left, sum);
        backtrack(root->right, sum);

        --prefixSum[sum];
    }
};

组合

LC77 组合

可以用回溯的方式。用k限制回溯树的深度。

code

class Solution {
private:
    int n;
    vector<int> comb;
    vector<vector<int>> combinations;
public:
    vector<vector<int>> combine(int n, int k) {
        this->n = n;
        backtrack(1, k);
        return combinations;
    }

    void backtrack(int i, int k)
    {
        if(k == 0)
        {
            combinations.push_back(comb);
            return;            
        }

        for(; i <= n; ++i)
        {
            comb.push_back(i);
            backtrack(i + 1, k - 1);
            comb.pop_back();
        }
    }
};

---

LC39 组合总数

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。所有数字（包括 target）都是正整数。解集不能包含重复的组合。

根据要求我们需要给结果集合去重。我们可以得到所有结果后对结果按字典序排序然后去重。更好的做法是在进行回溯的同时就进行去重。我们可以通过保证决策树的单调性来达到去重的目的（//TODO: 为什么？）。不允许深层作出的决策大于浅层作出的决策。

• 将candidates中的数组排序。
• 在遍历candidates数组的时候，传给下一个candidate的选择列表缩小1。（见代码）

优化：

• 在判断是否为有效的路径时，因为candidates已经排序，如果当前的candidate无效，后面的所有candidates > candidate，因此也是无效的。此时直接break循环即可。

code

class Solution {
private:
    vector<int> path;
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(candidates.begin(), candidates.end(), target);
        return res;
    }
    template<typename It>
    void backtrack(It first, It last, int target)
    {
        
        if(target == 0)
        {
            res.emplace_back(path.begin(), path.end());
            return;
        }

        while(first < last)
        {
            // check if this decision is valid
            if(target - *first < 0)
            {
                // if first is not valid, due to the candidates are
                // sorted, all the elements after first cannot be 
                // valid.
                break;
            } 

            // add the decision into the path
            path.push_back(*first);
            // dfs
            backtrack(first, last, target - *first);
            // cancel the decision
            path.pop_back();
            // move to next choice
            ++first;
        }
    }
};

---

LC40 组合总数II

和前一题基本一致。虽然数组总有重复的数字，但是不允许同一个数字被重复使用。所以除了通过排序去重外，还需要在每次的选择列表中去重。如果这一次的选择和上一次相同，那么就跳过。

code

class Solution {
private:
    vector<int> path{};
    vector<vector<int>> res{};
public:
    Solution()
    :path{}
    ,res{}
    {}

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrace(candidates.begin(), candidates.end(), target);
        return res;
    }
    template<typename It>
    void backtrace(It first, It last, int target)
    {
        // stop condition
        if(target == 0)
        {
            res.push_back(path);
        }

        int pre = -1;
        while(first < last)
        {
            // if *first is the same with last one
            if(pre == *first)
            {
                ++first;
                continue; 
            }
            pre = *first;

            // check if the choice is valid
            if(target - *first < 0) break;

            // add it into the path
            path.push_back(*first);
            backtrace(first + 1, last, target - *first);
            // cancel the choice
            path.pop_back();
            // move first
            ++first;
        }
    }
};

---

简单回溯

复原IP地址

LC93 复原IP地址

简单回溯。需要注意的是”00”不是一个有效的IP段，因此如果遇到第一个数就为0时，不应该继续向下分割字符串，否则会出现前置的0。

使用size_t和substr的版本 code

class Solution {
private:
    vector<string> res;
    string s;
public:
    vector<string> restoreIpAddresses(string s) {
        this->s = s;
        backtrace(0, s.size(), "", 0);
        return res;
    }

    void backtrace(size_t first, size_t last, string path, int n)
    {
        
        // stop condition
        if(first == last && n == 4)
        {
            res.push_back(path.substr(0, path.size() - 1));
        }

        if(!(first < last) || n > 4) return;

        for(size_t i = 1; i <= 3; ++i)
        { 
            auto num_str = s.substr(first, i);
            auto num = stoi(num_str);

            if(num > 255) break;

            auto new_path = path;
            // add num to path
            new_path += num_str;
            new_path += '.';

            backtrace(first + i, last, new_path, n + 1);

            if(i == 1 && num == 0) break;
        }
    }
};

使用Iterator的版本

class Solution {
private:
    vector<int> ip;
    vector<string> ips;
public:
    vector<string> restoreIpAddresses(string s) {
        backtrack(s.begin(), s.end());
        return ips;
    }

    template<typename It>
    void backtrack(It first, It last)
    {
        if(ip.size() == 4 && first < last)
        {
            return;
        }
        // fill in all four parts for an IP 
        // nothing left in the string
        if(ip.size() == 4 && first == last)
        {
            auto&& ip_str = string{};
            auto it = ip.begin();
            for(;it < --ip.end(); ++it)
            {
                ip_str += to_string(*it);
                ip_str += ".";
            }
            ip_str += to_string(*it);
            ips.emplace_back(move(ip_str));
        }

        for(auto it = first + 1; it <= last && it < first + 4; ++it)
        {
            auto part = string(first, it);
            auto num  = stoi(part);

            if(num <= 255)
            {
                ip.push_back(num);
                backtrack(it, last);
                ip.pop_back();
            }

            if(num == 0) break;
            
        }
    }
};

电话号码的字母组合

LC17 电话号码的字母组合

简单回溯。没有不合法的选择。注意结束条件满足，将path加入结果集合后要return。

code

class Solution {
private:
    string path;
    vector<string> res;
    vector<string> dict;
public:
    Solution()
    :path{}
    ,res{}
    ,dict{}
    {
        // 0 and 1 placeholders
        dict.emplace_back();
        dict.emplace_back();
        // 2 to 9
        dict.emplace_back("abc");
        dict.emplace_back("def");
        dict.emplace_back("ghi");
        dict.emplace_back("jkl");
        dict.emplace_back("mno");
        dict.emplace_back("pqrs");
        dict.emplace_back("tuv");
        dict.emplace_back("wxyz");
    }
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        backtrack(digits.begin(), digits.end());
        return res;
    }
    template<typename It>
    void backtrack(It first, It last)
    {
        
        // stop condition
        if(!(first < last))
        {
            res.push_back(path);
            return;
        }

        for(auto c : dict[*first - '0'])
        {
            path += c;
            backtrack(first + 1, last);
            path.pop_back();
        }
    }
};

括号生成

LC22 括号生成
简单回溯。每次决策只有两种。
注意：

• 回溯算法修改状态后，无论怎样都要恢复状态。除非你用函数栈来复制参数。

code

class Solution {
private:
    inline const static char L_PARENTHESIS = '(';
    inline const static char R_PARENTHESIS = ')';
    int p;
    pair<int, int> state;
    string path;
    vector<string> res;
public:
    Solution()
            :p{0}
            ,state{0,0}
            ,path{}
            ,res{}
    {}

    vector<string> generateParenthesis(int n) {
        p = n;
        backtrack();
        return res;
    }

    void backtrack()
    {
        // stop condition
        if(state.first == p && state.second == p)
        {
            res.push_back(path);
            return;
        }

        // make decisions
        // we could add left p if first < 3
        if(state.first < p)
        {
            ++state.first;
            path += L_PARENTHESIS;

            backtrack();
            --state.first;
            path.pop_back();
        }

        // we could add right if only left > right
        if(state.first > state.second)
        {
            ++state.second;
            path += R_PARENTHESIS;
            backtrack();
            --state.second;
            path.pop_back();
        }
    }
};

---

困难回溯

正则表达式匹配

LC10 正则表达式匹配

比较复杂的回溯。恢复状态比较麻烦，所以我们直接借助函数调用栈来拷贝参数。

• 如果p为空：
  • s为空，匹配成功
  • s不为空，匹配失败

[以下开始p非空，但s是否非空不确定]

• 如果p的第二个字符是*
  • 我们可以忽略p的前两个字符，匹配s和p.substr(2)
  • 如果s非空，我们可以检查p的第一个字符和s是否匹配，如果匹配，我们就进一步去匹配s.substr(1)和p
  • 如果以上两种情况都未匹配成功，则匹配失败。
• 如果p的第二个字符不是*
  • 如果s非空，我们检查p的第一个字符和s是否匹配，如果匹配，我们就进一步去匹配s.substr(1)和p.substr(1)
  • 否则匹配失败。
    code

    class Solution {
    public:
        bool isMatch(string s, string p) {
            if(p.empty())
            {
                return s.empty();
            }
    
            /* p is not empty below*/
    
            if(p.size() > 1 && p[1] == '*')
            {
                return 
                // ignore .* and (LETTER)*
                isMatch(s, p.substr(2)) ||
                // match the first letter of s with p, then forward s.
                (
                    // we have to make sure that s is not empty here
                    (!s.empty() && (s[0] == p[0] || p[0] == '.')) &&
                    isMatch(s.substr(1), p)
                );
            }
            else
            {
                return
                // p is not empty, then s must not be empty.
                !s.empty()                    && 
                // match the first letters
                (s[0] == p[0] || p[0] == '.') &&
                // match others
                isMatch(s.substr(1), p.substr(1));
            }
        }
    };

---

通配符匹配

LC44 通配符匹配

需要进行仔细剪枝的回溯，否则会导致TLE。暂且不知道该如何剪枝。

回溯TLE code

class Solution {
public:
    bool isMatch(string s, string p)
    {
        // remove duplicate '*'
        p.erase(unique(p.begin(), p.end(), [](auto lhs, auto rhs)
        {
            return lhs == '*' && rhs == '*';
        }), p.end());

        return isMatch_(s, p);
    }
    bool isMatch_(string s, string p) {
        if(p.empty()) return s.empty();

        if('*' == p[0])
        {
            return 
            // consider '*' as an empty string
            isMatch(s, p.substr(1)) ||
            // consider s[0] match with '*'
            (!s.empty() && isMatch(s.substr(1), p));
        }
        else
        {
            return 
            // s must not be empty
            !s.empty() &&
            (s[0] == p[0] || '?' == p[0]) &&
            isMatch(s.substr(1), p.substr(1));
        }
    }
};

可以通过贪婪的方式进行匹配（未证明，但是AC）：

遇到相同字符就直接匹配。
遇到通配符就不断扩大匹配长度直到匹配成功或者就算搜寻到匹配字符的尾没成功，那就匹配失败。

• 遇到相同字符 或 模式字符为'?'就直接匹配。
• 遇到模式字符为'*'，就记录下此时模式字符'*'的位置pStar和对应的匹配字符的位置iStar，将模式字符的指针向前移动(即尝试将'*'和空串匹配)，回到前一步。
• 如果曾经记录过模式字符中'*'的位置，但在第一步中匹配失败，说明'*'匹配的长度不够。我们应该增加'*'匹配字符串的长度，即将iStar向前移动，并将i回溯至iStar位置，j回溯至jStar + 1位置。
• 如果未曾记录过模式字符中的'*'却匹配失败，那就彻底失败了。

code

class Solution {
public:
    bool isMatch(string s, string p)
    {
        auto i = s.begin();
        auto j = p.begin();
        auto wc_i = s.end();
        auto wc_j = p.end();

        while(i != s.end())
        {
            // if i and j are the same 
            // of j is '?', just match
            if(*i == *j || '?' == *j)
            {
                ++i;
                ++j;
            }
            // if j is a wildcard, save its the pos for i & j
            else if('*' == *j)
            {
                wc_i = i;
                wc_j = j;
                // move j forward, get the wildcard 
                // ready for matching empty string
                ++j;
            }
            // if the pos for wc_j is not invalid, but we failed
            // in matching them, we have to backtrack
            else if(wc_j != p.end())
            {
                // move wc_i 1 pos forward
                // makes the wildcard to match more letters
                ++wc_i;
                i = wc_i;
                // get j back to the char after the wildcard
                j = wc_j + 1;
            }
            else
            {
                return false;
            }
        }

        // we have finished matching all char in s
        // we could accept the remaining chars in p are wildcards
        while(j != p.end() && *j == '*') ++j;
        return j == p.end();
    }
};

---

单词搜索

LC79 单词搜索

要求：同一个单元格内的字母不允许被重复使用。因此我们需要一个和原矩阵一样大的矩阵explored来记录哪些格子已经被探索了。
初始化一个和原矩阵一样大的矩阵，并标记所有元素为NOT_EXPLORED。在回溯函数中，注意标记EXPLORED和标记NOT_EXPLORED一定要成对出现，这样可以保证在[i, j]位置的一次探索结束后，explored仍然能恢复成全为NOT_EXPLORED的样子。

回溯函数传递当前探索的坐标[x, y]，已经查找到单词的第n位。

失败的情况：

• 如果 n > word.size() - 1，则已经无需再探索，返回false
• 如果 board[x][y] != word[n]，说明这一位找错了，返回false
• 如果 explored[x][y] != NOT_EXPLORED，说明走了回头路，返回false

成功的情况：

• 如果 n == word.size() - 1 && board[x][y] == word[n]，证明正好找到了，返回true

其他（继续探索的情况）：

• 标记该点为已探索
• 探索上下左右，只要有一个成功，那就成功了，剩下的就不要再去探索了。
• 标记该点为未探索
• 返回结果。

code

class Solution {
private:
    enum state
    {
        NOT_EXPLORED, EXPLORED
    };
    string word;
    vector<vector<state>> explored;
public:
    bool exist(vector<vector<char>>& board, string word) {
        this->word = word;
        bool res = false;

        explored = vector<vector<state>>(board.size(), 
        vector<state>(board.front().size(), NOT_EXPLORED));

        for(int i = 0; i < board.size(); ++i)
        {
            if(res) break;
            for(int j = 0; j < board.front().size(); ++j)
            {
                res = res || backtrack(board, 0, i, j);
                if(res) break;
            }
        }
        return res;
    }

    bool backtrack(const vector<vector<char>>& board, 
                   int n, int x, int y)
    {
        // we are on the wrong path
        if(n > word.size() - 1 || board[x][y] != word[n] || explored[x][y] != NOT_EXPLORED)
        {
            return false;
        }
        
        // we found the word
        else if(n == word.size() - 1 && board[x][y] == word[n])
        {
            return true;
        }

        // we are on the correct path, keep going
        else
        {
            explored[x][y] = EXPLORED;

            bool res = false;
            // move up
            if(x > 0 && !res)
            {
                res = res || backtrack(board, n + 1, x - 1, y);
            }
            // move down
            if(x < board.size() - 1 && !res)
            {
                res = res || backtrack(board, n + 1, x + 1, y);
            }
            // move left
            if(y > 0 && !res)
            {
                res = res || backtrack(board, n + 1, x, y - 1);
            }
            // move right
            if(y < board.front().size() - 1 && !res)
            {
                res = res || backtrack(board, n + 1, x, y + 1);
            }

            explored[x][y] = NOT_EXPLORED;
            return res;
        }
    }
};

---

所有可能的满二叉树

LC894 所有可能的满二叉树

• 满二叉树的节点个数一定为奇数
• 欲获得节点数为N的满二叉树：
  • 其左子树为节点数为$i = 1,3,5, \cdots ,N - 2$的所有可能满二叉树的集合
  • 当其左子树节点数为i时，其右子树的节点数必然为$N - 1 - i$，因为总节点数$N$ - 满叉树的根节点$1$ - 左子树的节点数$i$ $=0$
• 对所有可能性进行枚举即可。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if(N % 2 == 0)
        {
            return {};
        }
        return backtrace(N);
    }

    vector<TreeNode*> backtrace(int N)
    {
        if(N == 0)
        {
            return {nullptr};
        }

        // create a list for roots
        auto roots = vector<TreeNode*>{};

        // if it has no child
        if(N == 1)
        {
            auto root = new TreeNode{0};
            roots.push_back(root);
            return roots;
        }
        for(int i = 1; i < N; i+=2)
        {
            // if it has two children
            for(auto left : backtrace(i))
            {
                for(auto right : backtrace(N - 1 - i))
                {
                    auto root = new TreeNode{0};
                    root->left = left;
                    root->right = right;
                    roots.push_back(root);
                }
            }
        }
        return roots;
    }
};