题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { tree* head; if(sequence.empty()) return false; replace(sequence, head); houxubianli(head); cout<<"here is ok"<<endl; auto p1 = sequence.begin(); auto p2 = hx.begin(); auto p3=zx.begin(); for(auto i:hx) cout<<i<<':'; for(auto i:hx) cout<<i<<'~'; int j = sequence.size(); for (int i = 0; i < j; i++) { if(i<j-1) if(*(p3+i)>*(p3+i+1)) return false; cout<<*(p2+i)<<endl; if (*(p1 + i) != *(p2 + i)) return false; } return true; } //////////////////////////////////////////////////////////////////////////// /////////////////////////////////服务函数 vector <int> hx; vector <int> zx; struct tree { struct tree *left; struct tree *right; int val; }; /////////////////////////////////////////////////// /*之前的想法就是,根据后序遍历还原搜索二叉树,然后再后序遍历,和输出的数组对比来确定*/ /*但是现在有个问题,就是还原的树可能不是搜索二叉树,那肯定就是false的,但是后序遍历的对比是没问题*/ /*所以就在后序遍历中,增加对搜索二叉树的判断*/ void houxubianli(tree *head) { if(head) { if(head->left) houxubianli(head->left); cout<<head->val<<':'<<endl; zx.push_back(head->val); if(head->right) houxubianli(head->right); hx.push_back(head->val); cout<<head->val<<'-'<<endl; } } int replace(vector<int> sequence,tree* &head) { auto point = sequence.begin(); //point为迭代器,指向最后一个元素 int hou = sequence.size()-1; int qian = 0; point = point + hou; tree* p1 = new tree; //给新的节点开辟一个空间 head = p1; head->val = *point; head->left=nullptr; head->right=nullptr; cout<<head->val<<endl; if (hou<=0||qian>=hou) { return 1; } /*寻找左子树*/ for (int i = 1; hou-i>=0; i++) if (*(point - i) < *(point)) { vector<int> var(sequence.begin()+qian,sequence.begin()+hou-i+1); qian = hou - i+1; replace(var, head->left); break; } /*寻找右子树*/ if (*point < *(point - 1)) { vector<int> var2(sequence.begin() + qian, sequence.begin() + hou); replace(var2, head->right); } return 1; } };
这道题我一开始我的想法时,先根据数组的构建搜索二叉树,再后序遍历对比
要还原搜索二叉树,必须先找出后序遍历的搜索二叉树数组的规律.
1.根节点在数组的最后
2.节点是否有子树就看左边有没有数
3.节点如果有右子树,则左边第一个数就是他,必须大于它
4节点如果有左子树,则左边有小于它的树,也是第一个(从右往左第一个)
然后发现,根据数组构建的二叉树,后序遍历出来的二叉树,后序遍历还是数组本身
所以这个时候,根据搜索二叉树的中序遍历,数是递增的排列来判断.