L3-010. 是否完全二叉搜索树

wang 发表于 分类,标签: 天梯赛二叉树
 将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。输入格式:输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。输出格式:将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出“YES”,如果该树是完全二叉树;否则输出“NO”。输入样例1:938 45 42 24 58 30 67 12 51输出样例1:38 45 24 58 42 30 12 67 51YES输入样例2:838&nbs...

PAT (Advanced Level)1115. Counting Nodes in a BST (30)

发表于 分类,标签: pat二叉树
 ABinarySearchTree(BST)isrecursivelydefinedasabinarytreewhichhasthefollowingproperties:Theleftsubtreeofanodecontainsonlynodeswithkeyslessthanorequaltothenode'skey.Therightsubtreeofanodecontainsonlynodeswithkeysgreaterthanthenode'skey.Boththeleftandrightsubtreesmustalsobebinarysearchtrees.Insertasequenceofnumbersintoani...

PAT (Advanced Level)1119. Pre- and Post-order Traversals (30)

发表于 分类,标签: pat二叉树
 Supposethatallthekeysinabinarytreearedistinctpositiveintegers.Auniquebinarytreecanbedeterminedbyagivenpairofpostorderandinordertraversalsequences,orpreorderandinordertraversalsequences.However,ifonlythepostorderandpreordertraversalsequencesaregiven,thecorrespondingtreemaynolongerbeunique.Nowgivenapairofpostorderandpreordertraversa...

1102. Invert a Binary Tree (25)(pat甲级)

发表于 分类,标签: pat二叉树
 ThefollowingisfromMaxHowell@twitter:Google:90%ofourengineersusethesoftwareyouwrote(Homebrew),butyoucan'tinvertabinarytreeonawhiteboardsofuckoff.Nowit'syourturntoprovethatYOUCANinvertabinarytree!InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivesapositiveintegerN(<=10)whichisthetotalnumbe...

1110. Complete Binary Tree (25)(pat甲级)

发表于 分类,标签: pat二叉树
 Givenatree,youaresupposedtotellifitisacompletebinarytree.InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivesapositiveintegerN(<=20)whichisthetotalnumberofnodesinthetree--andhencethenodesarenumberedfrom0toN-1.ThenNlinesfollow,eachcorrespondstoanode,andgivestheindicesoftheleftandrightchild...

这是二叉搜索树吗?(区间递归)

发表于 分类,标签: 二叉树
 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,其左子树中所有结点的键值小于该结点的键值;其右子树中所有结点的键值大于等于该结点的键值;其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。输入格式:输入的第一行给出正整数N(<=1000)。随后一行给出N个整数键值,其间以空格分隔。输出格式:如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出“YES”,然后在下一行输出该树后序遍历的结果。数字间有1个空格,一行的首尾不得有多余空格。若答案是否,则输出“NO”。输入样例1:78 6 5 7 10 8 11输出样例1:YES5&nb...

树的遍历

发表于 分类,标签: 二叉树
 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式:输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式:在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。输入样例:72 3 1 5 7 6 41 2 3 4 5 6 7输出样例:4 1 6 3 5 7 2#include<iostream>#include<math.h>#include<stdio.h>#include&...