将leetcode中二叉树的数组结构转为真实的树结构

我们在 LeetCode 上锻炼算法时，关于二叉树的题目，网站上给的都直接是一个数组，那么本地测试的时候，就很不方便。

官方文档中的解释是这样的：请问 [1, null, 2, 3] 在二叉树测试用例中代表什么。

1. javascript 版本 #

我们首先定义一个 TreeNode 的结构：

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

我们用循环的方式，将数组转为二叉树结构。

const array2binary = (arr) => {
  if (!arr || !arr.length) {
    return null;
  }
  let index = 0;
  const queue = [];
  const len = arr.length;
  const head = new TreeNode(arr[index]);
  queue.push(head);

  while (index < len) {
    index++;
    const parent = queue.shift();
    if (arr[index] !== null && arr[index] !== undefined) {
      const node = new TreeNode(arr[index]);
      parent.left = node;
      queue.push(node);
    }

    index++;
    if (arr[index] !== null && arr[index] !== undefined) {
      const node = new TreeNode(arr[index]);
      parent.right = node;
      queue.push(node);
    }
  }
  return head;
};

使用：

const root = array2binary([3, 9, 20, null, null, 15, 7]);

最终转换成的树形结构：

2.C++ 版本 #

在 C++中的 vector 数据结构里，只能有一种类型，这里我们用INT_MAX来代替 null，需要转换的数组中的 null 也请用 INT_MAX 来代替。

我们的转换程序主要是应用在本地，为了方便本地的调试，因此在使用时，尤其要注意数据的范围，若真的用到了 INT_MAX 对应的数据，请把转换程序中代替 null 的INT_MAX更换为其他数字。

官方给的二叉树结构为：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

我们的转换程序如下：

/**
 * 将leetcode中的数组转为二叉树
 * 因C++中的vector只能是同一个类型，这里用INT_MAX来代替null
 * @param {vector<int>} nums
 * @return {TreeNode}
 */
TreeNode *vectorToTree(vector<int> nums) {
    int i = 1;
    bool isLeftTree = true; // 是否是左分支，true为左分支，false时是右分支

    if (nums.size() == 0) {
        return nullptr;
    }
    queue<TreeNode *> myQueue;
    TreeNode *head = new TreeNode(nums[0]);
    myQueue.push(head);

    while (i < nums.size()) {
        TreeNode *topNode = myQueue.front();

        // 这里我们与js版稍微有点区别
        // 队列中的节点只要用两次，当isLeftTree指向到右分支时，说明可以取出了
        if (!isLeftTree) {
            myQueue.pop();
        }

        // 我们用INT_MAX来标识nullptr
        if (nums[i] != INT_MAX) {
            TreeNode *node = new TreeNode(nums[i]);

            if (isLeftTree) {
                topNode->left = node;
            } else {
                topNode->right = node;
            }
            myQueue.push(node);
        }
        isLeftTree = !isLeftTree;
        i++;
    }
    return head;
}

使用：

vector<int> nums = {3, 9, 20, INT_MAX, INT_MAX, 15, 7};

TreeeNode *root = vectorToTree(nums);

3. 测试 #

我们可以在 leetcode 中选择一个题目来测试下，就选最简单的二叉树前序遍历。

把题目中给到的数组数据，转为二叉树数据，然后再调试您的程序吧。

4. 题外话 #

刚开始经同事提示，添加了一个递归的方式，如：

// 错误代码，请不要直接使用
const array2binary = (arr, index = 0) => {
  if (!arr || arr[index] === null || index >= arr.length) {
    return null;
  }
  const node = new TreeNode(arr[index]);
  node.left = array2binary(arr, index * 2 + 1);
  node.right = array2binary(arr, index * 2 + 2);

  return node;
};

这个代码只会在某些情况里正常，并不会适应 leetcode 里所有的二叉树的情况。如在513. 找树左下角的值中的第 2 个示例：

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

实际的树结构是：

若使用最上面的迭代循环方式，是没有问题的，构建出来的树与例题中一样。但若使用这段递归的代码，就会出现问题，发现节点7没了。

这是因为：节点 2 的右子节点为 null 时，后续数组不会再用 null 为该空节点（2 右） 来填充他的子节点。使用上面队列结构循环时，我们会跳过（2 右）这个节点，接着处理节点 5。

但在递归的方式中，我们通过index * 2 + 1和index * 2 + 2来计算 arr[index]的左右节点，会把节点 7 算到（2 右）空节点的子节点上。从这里开始，后续的节点都会错位。

后来又想着怎么给这个递归程序补救一下，不过没找到实现的方式。