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

蚊子前端博客
发布于 2021-06-07 17:39
将leetcode中二叉树的数组结构转为真实的树结构

我们在 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]);

最终转换成的树形结构:

array2binary-蚊子的前端博客

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 + 1index * 2 + 2来计算 arr[index]的左右节点,会把节点 7 算到(2 右)空节点的子节点上。从这里开始,后续的节点都会错位。

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

标签:
阅读(905)

公众号:

qrcode

微信公众号:前端小茶馆

相关文章

公众号:

qrcode

微信公众号:前端小茶馆