23. 二叉树的高度

23. 二叉树的高度

题目描述
现给定一棵二叉树的先序遍历序列和中序遍历序列，要求你计算该二叉树的高度。

输入描述
输入包含多组测试数据，每组输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出描述
对于每组输入，输出一个整数，即该二叉树的高度。

输入示例
9
ABDFGHIEC
FDHGIBEAC
7
Abcdefg
gfedcbA
输出示例
5
7

实现代码（Python）:

importsysfromcollectionsimportdequeclassTreeNode(object):def__init__(self,val,left=None,right=None):self.val=val self.left=left self.right=rightdefCreateTree(pre_seq,mid_seq):#创建二叉树,二叉树的定义其实就是一个递归定义ifnotpre_seqornotmid_seq:#递归终止条件returnNone#获取根节点元素root_val=pre_seq[0]#创建根节点root=TreeNode(root_val)#找到中序中根节点下标，方便划分左右子树root_idx=mid_seq.index(root_val)#递归创建左子树root.left=CreateTree(pre_seq[1:root_idx+1],mid_seq[:root_idx])#递归创建右子树root.right=CreateTree(pre_seq[root_idx+1:],mid_seq[root_idx+1:])returnrootdefTreeHeight(root):#利用层序遍历求树高ifnotroot:return0queue=deque([root])res=[]whilequeue:level=[]size=len(queue)for_inrange(size):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnlen(res)defmain():lines=sys.stdin.read().splitlines()count=len(lines)//3idx=0for_inrange(count):n=int(lines[idx])idx+=1pre_seq=lines[idx]idx+=1mid_seq=lines[idx]idx+=1root=CreateTree(pre_seq,mid_seq)height=TreeHeight(root)print(height)if__name__=="__main__":main()

分析

创建二叉树：
1.递归终止条件：先序 / 中序序列为空时，返回None（无节点）；
2.根节点确定：先序第一个元素是根节点；
3.划分左右子树：通过中序中根节点的索引，拆分出左 / 右子树的先序、中序序列；
4.递归构建：分别构建左、右子树并挂载到根节点。

求树高可通过层序遍历或前中后序遍历