深圳网站ui设计,永康网站建设的公司,网站详情页设计,建设个人网站的参考网站及文献前序中序遍历构造二叉树 思路
在前序中找根结点根据根结点 中序#xff0c;分成左右两棵子树根据子树长度#xff0c;把前序分成左右两颗子树递归处理子树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* s…前序中序遍历构造二叉树 思路
在前序中找根结点根据根结点 中序分成左右两棵子树根据子树长度把前序分成左右两颗子树递归处理子树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){assert(preorderSize inorderSize);if (preorderSize 0){return NULL;}//从前序遍历中找到根结点int rootValue preorder[0];//根据根的值在中序遍历中找到其下标int rindex -1;for (int i 0; i inorderSize; i){//假设树的结点不重复if (inorder[i] rootValue){rindex i;}}assert(rindex ! -1);//创建根struct TreeNode* root (struct TreeNode *)malloc(sizeof(struct TreeNode));root-valrootValue;//创建左子树root-left buildTree(preorder1,rindex,inorder,rindex);//创建右子树root-right buildTree(preorder1rindex,preorderSize-1-rindex,inorderrindex1,inorderSize-rindex-1);return root;
}
