陈恒承

894. 所有可能的满二叉树

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

---

这道题怎么说呢？涉及的点如下：

• 树的构建
• 递归遍历

真的是很难理解，也很难想出来。我只能参考别人的解法来学习了。思路如下：
首先，我们先分析一下，n=1,n=3,n=5 时，构建树的情况如下

n=1

0

n=3

 0
0 0

n=5

   0        0
 0   0    0   0
0 0         0   0

观察可知，

当 n=3 时，有一种情况 :

• 左子树 的节点数量有 1 个，右子树有 1 个

当 n=5 时，有两种情况：

• 左子树 的节点数量有 3 个，右子树有 1 个
• 左子树 的节点数量有 1 个，右子树有 3 个
  

我们只要 把左子树与右子树的组合方式结合起来就可以了。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var allPossibleFBT = function (n) {
  let dp = [];
  if (n % 2 == 0) return dp;
  if (n === 1) {
    dp.push(new TreeNode(0));
    return dp;
  }
  for (let i = 1; i <= n - 2; i = i + 2) {
    const left = allPossibleFBT(i);
    const right = allPossibleFBT(n - i - 1);

    for (const x of left) {
      for (const y of right) {
        // 先构建 根节点..
        const root = new TreeNode(0);
        // 构建左子树
        root.left = x;
        // 建构右子树
        root.right = y;
        dp.push(root);
      }
    }
  }

  return dp;
};

教训小结

• 一般求构建树的组合，要想到用递归的方式，左子树组合 * 右子树组合

• 构建树，要从根节点开始构建

• 借助递归（终止条件，返回结果）

• 一定要注意左右子树（必然借助递归）

• 树的多种形式，必然是左右子树组合。。

• 不同的二叉搜索树 相类似