二叉树题目 ----7 前序中序遍历构造二叉树

前序中序遍历构造二叉树

思路

在前序中找根结点

根据根结点 + 中序，分成左右两棵子树

根据子树长度，把前序分成左右两颗子树

递归处理子树

/*** 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->val=rootValue;//创建左子树root->left = buildTree(preorder+1,rindex,inorder,rindex);//创建右子树root->right = buildTree(preorder+1+rindex,preorderSize-1-rindex,inorder+rindex+1,inorderSize-rindex-1);return root; }

总结

以上是生活随笔为你收集整理的二叉树题目 ----7 前序中序遍历构造二叉树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。