二叉搜索树的后序遍历序列

电脑杂谈  发布时间:2019-08-13 10:03:45  来源:网络整理

用文字描述先(根)序的遍历二叉树算法算法,中(根)序的遍历二_二叉树的层次遍历_二叉排序树中序遍历

面试题:二叉搜索树的后序遍历序列

范文:输入一个整数元组,分析该主键是不是某二叉搜索树的后序遍历结果。如果是刚离开true,如果离开false。假设输入的异或的任意两个数字都互不相同。

正确答案:

例如输入向量{5,7,6,9,11,10,8},则前往true,因为这个小数序列是下图二叉搜索树的后序遍历结果。如果输入的异或是{7,4,6,5},由于没有哪棵二叉搜索树的后序遍历的结果是这个序列,即使前往false。

上图是后序遍历序列5、7、6、9、1 1、10、8对应的二叉搜索树 在后序遍历得到的序列中,最后一个数字是树的根节点的值。数组中左边的数字可以分为两部份:第一部分是左子树结点的值,这些都比根节点的值小;第二部分是右子树结点的值,这些都比根节点的值大。 以向量{5,7,6,9二叉排序树中序遍历,11,10,8)为例,后序遍历结果的最后一个数字8就是根节点的值。在这个函数中,前3个数字5、7和6都比8小,是值为8的节点的左子树节点;后3个数字9、11和10都比8大,是值为8的节点的右子树结点。 我们接下来用同样的原理确认与函数每一部分对应的子树的结构。这本来就是一个递归的过程。对于序列5、7、6,最后一个数字6是左子树的根节点的值。数字5比6小,是值为6的节点的左子结点,而7则是它的右子结点。同样,在序列9、11、10中,最后一个数字10是右子树的根节点,数字9比10小,是值为10的节点的左子结点,而11则是它的右子结点。 我们再来判断另一个整数元组{7,4,6,5)。后序遍历的最后一个数是根节点,即使根节点的值是5。由于第一个数字7大于5二叉排序树中序遍历,即使在对应的二叉搜索树中,根节点上是没有左子树的,数字7、4和6都是右子树结点的值。但我们发现在右子树中有一个结点的值是4,比根节点的值5小,这违反了二叉搜索树的概念。因此不存在一棵二叉搜索树,它的后序遍历的结果是7、4、6、5。 找到了规律之后再写代码,就不是一件很困难的大事了。下面是参考源码

class Solution

{

public:

bool IsBST(vector<int> sequence)

{

用文字描述先(根)序的遍历二叉树算法算法,中(根)序的遍历二_二叉树的层次遍历_二叉排序树中序遍历

int n = sequence.size();

if (n == 1 || n == )

{

return true;

}

int root = sequence[n-1];

vector<int> leftSequence;

vector<int> rightSequence;

int i = ;

for (;i < n-1;++i)

二叉树的层次遍历_用文字描述先(根)序的遍历二叉树算法算法,中(根)序的遍历二_二叉排序树中序遍历

{

if (sequence[i] <= root)

{

leftSequence.push_back(sequence[i]);

}

else

{

break;

}

}

二叉树的层次遍历_用文字描述先(根)序的遍历二叉树算法算法,中(根)序的遍历二_二叉排序树中序遍历

for (;i < n-1;++i)

{

if (sequence[i] > root)

{

rightSequence.push_back(sequence[i]);

}

else

{

return false;

}

二叉树的层次遍历_用文字描述先(根)序的遍历二叉树算法算法,中(根)序的遍历二_二叉排序树中序遍历

}

return IsBST(leftSequence) && IsBST(rightSequence);

}

//分析sequence是不是二叉树的后序遍历序列

bool VerifySquenceOfBST(vector<int> sequence)

{

int n = sequence.size();

if (n == )

{

return false;

}

return IsBST(sequence);

}

};


本文来自电脑杂谈,转载请注明本文网址:
http://xinshanjie.com/a/jisuanjixue/article-119082-1.html

    发表评论  请自觉遵守互联网相关的政策法规,严禁发布、暴力、反动的言论

    热点图片
    拼命载入中...