- 题目:根据中序和后序遍历构建二叉树
- 思路:利用递归加上分治的思想。先找到根节点的值,然后在根据中序遍历找到根节点的左右两边的值,然后在递归的处理左右两边的左右子树。这里的关键在于怎么处理递归的左右子树的范围,代码里面详细解释
- 代码:
class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { vector<int>::size_type lenIn = inorder.size(); vector<int>::size_type lenPost = postorder.size(); return buildTree_Aux(inorder,0,lenIn-1,postorder,0,lenPost-1); } TreeNode *buildTree_Aux(vector<int> &inorder,int inB,int inE, vector<int> &postorder,int poB,int poE) { if(inB > inE || poB > poE) return NULL; //在后序遍历中确定根节点 TreeNode* root = new TreeNode(postorder[poE]); //在中序遍历中确定左右子树 vector<int>::iterator iter = find(inorder.begin()+inB,inorder.begin()+inE,postorder[poE]); int index = iter - inorder.begin();//根节点的位置
root->left = buildTree_Aux(inorder,inB,index-1,postorder,poB,poB+index-1-inB);
//这里postorder,poB,poB+index-1-inB这部分表示后序的左子树。pob是开始位置,index-1-inB是后序左子树的节点数的个数。poB+index-1-inB是后序的左子树的尾部 root->right = buildTree_Aux(inorder,index+1,inE,postorder,poB+index-inB,poE-1);
//这里postorder,poB+index-inB,poE-1这部分表示后序的右子树。poB+index-inB右子树开始位置,poE-1右子树结束位置,去掉了根节点的值(最尾部) return root; } }; - 题目:根据前序和中序遍历构建二叉树
- 思路:类似
- 代码:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { vector<int>::size_type lenIn = inorder.size(); vector<int>::size_type lenPre = preorder.size(); return buildTree_Aux(preorder, 0, lenPre-1, inorder, 0, lenIn-1); } TreeNode *buildTree_Aux(vector<int> &preorder,int prb,int pre, vector<int> &inorder,int inb,int ine) { if (prb > pre || inb > ine) return NULL; TreeNode *root = new TreeNode(preorder[prb]); vector<int>::iterator iter = find(inorder.begin()+inb,inorder.begin()+ine,preorder[pre]); int mid = iter - inorder.begin(); root->left = buildTree_Aux(preorder, prb+1, prb+mid-inb, inorder, inb, mid-1); root->right = buildTree_Aux(preorder, prb+1+mid-inb, pre, inorder, mid+1, ine); return root; } };
今天的文章根据中序和后序确定二叉树_根据前序和中序构建二叉树Java分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/45829.html