二叉树还原【前序+中序】【后续+中序】

已知二叉树的中序加前序或后续可以还原出二叉树(:中序是必须知道的)

二叉树还原【前序+中序】【后续+中序】

前序:a b c

中序:b a c

后续:b c a

1. 前序 + 中序

思路

对于例图中,由前序可知,第一个元素即a是根节点,从对应的中序中找到a。从而进一步知道其左边的b在左树中,其右边的c在右树中,这样结合前序递归可以还原出整个树。

参考代码

/** * 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* getTree(vector<int> &preorder, vector<int> &inorder, int prebeg, int preend, int inbeg, int inend) { if(prebeg < preend && inbeg < inend) { TreeNode *rev = new TreeNode(preorder[prebeg]); vector<int>::iterator mid = find(inorder.begin()+inbeg, inorder.begin()+inend, preorder[prebeg]); int span = mid - (inorder.begin() + inbeg); rev->left = getTree(preorder, inorder, prebeg+1, prebeg+1+span, inbeg, inbeg+span); rev->right = getTree(preorder, inorder, prebeg+1+span, preend, inbeg+span+1, inend); return rev; } return NULL; } TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { return getTree(preorder, inorder, 0, preorder.size(), 0, inorder.size()); } };

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzgspf.html