题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param preOrder int整型一维数组 * @param preOrderLen int preOrder数组长度 * @param vinOrder int整型一维数组 * @param vinOrderLen int vinOrder数组长度 * @return TreeNode类 */ #include <stdio.h> int searchArr(int *Arr, int ArrLen, int p) { int i; for(i=0;i<ArrLen;i++) { if(p==Arr[i]) return i; } return -1; } struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) { struct TreeNode* res; int leftTreeLen, rightTreeLen; if(!preOrderLen) return NULL; res = (struct TreeNode*)malloc(sizeof(struct TreeNode)); res->val = preOrder[0]; leftTreeLen = searchArr(vinOrder, vinOrderLen, preOrder[0]); rightTreeLen = preOrderLen-1-leftTreeLen; res->left = reConstructBinaryTree(preOrder+1, leftTreeLen, vinOrder, leftTreeLen); res->right = reConstructBinaryTree(preOrder+1+leftTreeLen, rightTreeLen, vinOrder+leftTreeLen+1, rightTreeLen); return res; }