23. 二叉树的高度

23. 二叉树的高度题目描述现给定一棵二叉树的先序遍历序列和中序遍历序列要求你计算该二叉树的高度。输入描述输入包含多组测试数据每组输入首先给出正整数N50为树中结点总数。下面2行先后给出先序和中序遍历序列均是长度为N的不包含重复英文字母区别大小写的字符串。输出描述对于每组输入输出一个整数即该二叉树的高度。输入示例9ABDFGHIECFDHGIBEAC7AbcdefggfedcbA输出示例57实现代码Python:importsysfromcollectionsimportdequeclassTreeNode(object):def__init__(self,val,leftNone,rightNone):self.valval self.leftleft self.rightrightdefCreateTree(pre_seq,mid_seq):#创建二叉树,二叉树的定义其实就是一个递归定义ifnotpre_seqornotmid_seq:#递归终止条件returnNone#获取根节点元素root_valpre_seq[0]#创建根节点rootTreeNode(root_val)#找到中序中根节点下标方便划分左右子树root_idxmid_seq.index(root_val)#递归创建左子树root.leftCreateTree(pre_seq[1:root_idx1],mid_seq[:root_idx])#递归创建右子树root.rightCreateTree(pre_seq[root_idx1:],mid_seq[root_idx1:])returnrootdefTreeHeight(root):#利用层序遍历求树高ifnotroot:return0queuedeque([root])res[]whilequeue:level[]sizelen(queue)for_inrange(size):nodequeue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnlen(res)defmain():linessys.stdin.read().splitlines()countlen(lines)//3idx0for_inrange(count):nint(lines[idx])idx1pre_seqlines[idx]idx1mid_seqlines[idx]idx1rootCreateTree(pre_seq,mid_seq)heightTreeHeight(root)print(height)if__name____main__:main()分析创建二叉树1.递归终止条件先序 / 中序序列为空时返回None无节点2.根节点确定先序第一个元素是根节点3.划分左右子树通过中序中根节点的索引拆分出左 / 右子树的先序、中序序列4.递归构建分别构建左、右子树并挂载到根节点。求树高可通过层序遍历或前中后序遍历