下面序列哪个不可能是二叉搜索时的后序遍历结果?
A. 1,2,3,4,5
B. 3,5,1,4,2
C. 1,2,5,4,3
D. 5,4,3,2,1
二叉搜索树 ,
根节点是2,剩下的元素是3, 5, 1, 4。根据BST的性质,所有小于2的元素应该在左子树,所有大于2的元素应该在右子树。
分析剩下的元素:3, 5, 1, 4;按顺序看,1在5前面,但1小于2,不符合BST的性质。
B 首先我们观察题目:二叉搜...
用户登录可进行刷题及查看答案
B 首先我们观察题目:二叉搜索树,后序遍历两个知识点。
二叉搜索树,用于搜索,因此 内部节点没有重复的元素 。另外, 满足二叉树的性质,左子树都比自己小,右子树都比自己大。 那么 可想而知,如果按照后序遍历,先左后右最后自己的顺序来遍历树,数组的最后一个元素肯定是自己(父节点),然后剩余的部分分成两个部分,第一部分都比自己小(左子树部分),第二部分都比自己大(右子树部分),因此套用这个关系就可以循环检验出是否是二叉搜索树的后序遍历了。
登录后提交答案