Sicily1210.二叉树题解

惊闻期末考试换回sicily，不由得大吃一惊，之前被leetcode惯坏了，赶紧回到sicily练练手吧。

1. 题目描述

在众多的数据结构中，二叉树是一种特殊而重要的结构，有着广泛的应用。二叉树或者是一个结点，或者有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 遍历一棵二叉树就是按某条搜索路径巡访其中每个结点，使得每个结点均被访问一次，而且仅被访问一次。最常使用的有三种遍历的方式：

１．前序遍历：若二叉树为空，则空操作；否则先访问根结点，接着前序遍历左子树，最后再前序遍历右子树。２．中序遍历：若二叉树为空，则空操作；否则先中序遍历左子树，接着访问根结点，最后再前中遍历右子树。３．后序遍历：若二叉树为空，则空操作；否则先后序遍历左子树，接着后序遍历右子树，最后再访问根结点。

例如图(1)所示的二叉树： 前序遍历的顺序是ABCD，中序遍历的顺序是CBAD，后序遍历的顺序是CBDA。 对一棵二叉树，如果给出前序遍历和中许遍历的结点访问顺序，那么后序遍历的顺序是唯一确定的，也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序，中序遍历的顺序是不确定的，例如：前序遍历的顺序是ABCD，而后序遍历的顺序是CBDA，那么就有两课二叉树满足这样的顺序（见图(1)和图(2)）。 现在的问题是：给定前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。

2. 样例

【Input】： 整个输入有两行，第一行给出前序遍历的访问顺序，第二行给出后序遍历的访问顺序。二叉树的结点用一个大写字母表示，不会有两个结点标上相同字母。输入数据不包含空格，且保证至少有一棵二叉树符合要求。 【Output】： 输出一个整数，为符合要求的不同形态二叉树的数目。

Input： ABCD CBDA Output： 2

3. 分析

这道题目很好地带我们温习了一下二叉树前序、中序和后序遍历的情况，然后结合这三种遍历的特点做一些计算。 前序和中序、后序和中序搭配都能唯一确定一棵二叉树，当前序和后序搭配的时候会出现不确定的情况，在第1部分已经举例说明了。 我们通过观察和分析可以得到以下结论：

前序遍历的第一个节点和后序遍历的最后一个节点相同，都是根节点；前序遍历的顺序是：根-左子树-右子树，后序遍历的顺序是：左子树-右子树-根；假设前序遍历的子树为节点a1-b1，后序遍历的子树为节点a2-b2，前序遍历的节点情况是字符串A，后序遍历的字符串是B，那么如果A[a1+1]与B[b2-1]相等，那么说明原来的父亲节点只有一个子树，而没有左右子树，就是类似一条线走下来那种，因此这里就可能存在2种可能的姿态啦，计数器counter+1；相同条件下，如果A[a1+1]与B[b2-1]不相等，那么说明原来的父亲节点有左右两个子树才会出现这种情况，那么此父亲节点是没有其他可能的姿态的，于是就继续遍历父亲节点下的左右两个子树，重复上一步操作；当a1 <= b1的时候，当前节点没有孩子了，结束递归；此时得到的counter代表了一共出现过counter次父亲节点只有一个子树的情况，每次出现这种情况就有2种可能（到底是左孩子还是右孩子）。因此最终的结果就是 2counter 种不同的子树。

4. 源码

/* * main.cpp * * Created on: 2017年6月7日 * Author: liboyang */ #include <iostream> #include <string> using namespace std; void getResult(string A, string B, int a1, int b1, int a2, int b2); int Pow(int n); int counter = 0; int main() { string A, B; while(cin >> A >> B) { getResult(A, B, 0, A.length()-1, 0, B.length()-1); cout << Pow(counter); } return 0; } void getResult(string A, string B, int a1, int b1, int a2, int b2) { if (a1 >= b1) { return; } int i; for (i = a2; i <= b2-1; i++) { if (A[a1+1] == B[i]) { break; } } /* 当前父节点只有一个孩子，有左右孩子两种情况 */ if (i == b2 - 1) { counter++; } getResult(A, B, a1+1, a1+1+i-a2, a2, i); getResult(A, B, a1+1+i-a2+1, b1, i+1, b2-1); } /* 幂计算 */ int Pow(int n) { int m = 1; for(int i = 0; i < n; i++) { m *= 2; } return m; }

5. 心得

改回了sicily不太习惯，自己写main函数以及多个测试样例输入等等，题目本身还是有一定难度的。