Codewars进阶之路——Fun with trees: array to tree

题意大概也就是给你一个向量，然后创建一个完全二叉树 之前不管什么二叉树的创建都是直接用递归，简单又快捷，同样如果只是针对这个结果也能很快写出对应的代码 先贴出我自己的TreeNode类：

class TreeNode { public: int m_value; TreeNode* m_left, *m_right; TreeNode(int value, TreeNode* left, TreeNode* right) :m_value(value), m_left(left), m_right(right){} TreeNode(int value) :m_value(value), m_left(NULL), m_right(NULL){} };

下面是用递归的方法创建完全二叉树：

void CreateTree(TreeNode *res,vector<int> a,int len,int pos) //从数组a中创建二叉树，len为向量a的长度。pos表示当前位置 { if(pos>len) return; (*res)=(BiTree)malloc(sizeof(TreeNode)); (*res)->m_value=a[pos]; CreateTree(&((*res)->m_left),a,len,2*pos+1); CreateTree(&((*res)->m_right),a,len,2*pos+2); }

这样就能创建完成了，但是看到codewars上给的初始函数static TreeNode* arrayToTree(std::vector arr) 一时很难往递归的方向下手，于是一狠心来了个非递归的方法：

class Solution { public: static TreeNode *arrayToTree(std::vector<int> arr) { if(arr.size() == 0) return NULL; int begin = 0, len = arr.size(); TreeNode *tree, *sp; unsigned long way; char i, j; tree = new TreeNode(arr[begin++]); for (way = 2, i = 1; begin < len; begin++, way++) { if (!((way >> i) & 1))i++; for (j = i - 1, sp = tree; 1; j--) { if (way&(1 << j)) { if (sp->m_right)sp = sp->m_right; else { sp->m_right = new TreeNode(arr[begin]); break; } } else { if (sp->m_left)sp = sp->m_left; else { sp->m_left = new TreeNode(arr[begin]); break; } } } } return tree; } };

思路如下： 首先判断参数arr是否为空，若空则直接返回NULL，否则进行如下操作： 若根节点标记为1，则根节点的左儿子为2，右儿子为3，以此类推，这部分用way表示，而i就存了所在的层数，然后每次都遍历一遍直到找到可供插入的节点。这样做会比较耗时间，后来通过测试以后看了别人的Solution，是真的简单，可以通过队列，也可以另外构造一个函数再进行简单的递归调用创建，这里就不贴了。