我们在 LeetCode 上锻炼算法时,关于二叉树的题目,网站上给的都直接是一个数组,那么本地测试的时候,就很不方便。
官方文档中的解释是这样的:请问 [1, null, 2, 3] 在二叉树测试用例中代表什么。
1. javascript 版本
我们首先定义一个 TreeNode 的结构:
COPYJAVASCRIPT
function TreeNode(val) { this.val = val; this.left = this.right = null; }
我们用循环的方式,将数组转为二叉树结构。
COPYJAVASCRIPT
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; };
使用:
COPYJAVASCRIPT
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
更换为其他数字。
官方给的二叉树结构为:
COPYCPP
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) {} };
我们的转换程序如下:
COPYCPP
/** * 将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; }
使用:
COPYCPP
vector<int> nums = {3, 9, 20, INT_MAX, INT_MAX, 15, 7}; TreeeNode *root = vectorToTree(nums);
3. 测试
我们可以在 leetcode 中选择一个题目来测试下,就选最简单的二叉树前序遍历。
把题目中给到的数组数据,转为二叉树数据,然后再调试您的程序吧。
4. 题外话
刚开始经同事提示,添加了一个递归的方式,如:
COPYJAVASCRIPT
// 错误代码,请不要直接使用 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 个示例:
COPYSHELL
输入: [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 右)空节点的子节点上。从这里开始,后续的节点都会错位。
后来又想着怎么给这个递归程序补救一下,不过没找到实现的方式。