這是什麼

簡單來說，函式（Function）呼叫自己的操作方式，在之前 DFS 解題時便採用這方法來搜尋節點。

遞迴有趣的地方有兩點：

• 理論上遞迴（Recursive）與迴圈（Iterative）可以處理相同的問題，只是寫法不同。
• 遞迴因為會不斷呼叫自己，假如函式本身會使用記憶體，那有可能因為呼叫自己的次數過多、記憶體佔用過多，導致 stack overflow。

刷題：894. All Possible Full Binary Trees

題目

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Note:

• 1 <= N <= 20

思考

很經典的 Recursion 題目，不斷呼叫函式來建立對應的節點並且組裝起來。

解題

JS

/**
 * @param {number} N
 * @return {TreeNode[]}
 */
const allPossibleFBT = (N) => {
  /**
   * @type {TreeNode[]}
   */
  let result = [];

  if (N === 1) {
    result.push(new TreeNode(0));
    return result;
  }

  N = N - 1;

  for (let i = 1; i < N; i += 2) {
    let left = allPossibleFBT(i);
    let right = allPossibleFBT(N - i);

    left.forEach(lNode => {
      right.forEach(rNode => {
        let currentNode = new TreeNode(0);
        currentNode.left = lNode;
        currentNode.right = rNode;
        result.push(currentNode);
      });
    });
  }

  return result;
};

Java

class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> result = new ArrayList<>();

        if (N == 1) {
            result.add(new TreeNode(0));
            return result;
        }

        N = N - 1;

        for (int i = 1; i < N; i += 2) {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(N - i);

            for (TreeNode lNode : left) {
                for (TreeNode rNode : right) {
                    TreeNode currentNode = new TreeNode(0);
                    currentNode.left = lNode;
                    currentNode.right = rNode;
                    result.add(currentNode);
                }
            }
        }

        return result;
    }
}

C

來源

struct TreeNode **helper(int N, int* returnSize, struct TreeNode ***fbt, int *fbtSize)
{
    struct TreeNode **ret = malloc(sizeof(struct TreeNode*));
    *returnSize = 0;

    if (N == 1)
    {
        struct TreeNode *root = calloc(1, sizeof(struct TreeNode));
        ret = realloc(ret, sizeof(struct TreeNode) * ((*returnSize) + 1));
        ret[*returnSize] = root;
        *returnSize++;
        return ret;
    }

    for (int i = 1; i <= N - 2; i += 2)
    {
        int lSize = fbtSize[i], rSize = fbtSize[N - i - 1];

        for (int j = 0; j < lSize; j++)
        {
            for (int k = 0; k < rSize; k++)
            {
                struct TreeNode *root = calloc(1, sizeof(struct TreeNode));
                root->left = fbt[i][j];
                root->right = fbt[N - i - 1][k];
                ret = realloc(ret, sizeof(struct TreeNode) * ((*returnSize) + 1));
                ret[*returnSize] = root;
                *returnSize++;
            }
        }
    }

    return ret;
}

struct TreeNode **allPossibleFBT(int N, int *returnSize)
{
    if (N % 2 == 0)
    {
        *returnSize = 0;
        return NULL;
    }

    struct TreeNode **fbt[21];
    int fbtSize[21] = {0};

    for (int i = 1; i <= N; i += 2)
    {
        int tmpSize = 0;
        fbt[i] = helper(i, &tmpSize, fbt, fbtSize);
        fbtSize[i] = tmpSize;
    }

    *returnSize = fbtSize[N];
    return fbt[N];
}

看法

JS 與 Java 在製作上簡單許多，了解如何使用遞迴即可完成。
可怕的反倒是 C，光是要如何動態製作陣列，就是個大問題。就由這題才了解到 calloc & realloc 的應用，深深感受到經驗不夠。

結論

遞迴的題目彈性大，需要的反倒是邏輯上的訓練，訓練出看出題目規律的能耐。
講這麼多，需要的仍然是更多的練習、更多的思考才能精進。