【二叉樹】先序序列為a,b,c,d 的不同二叉樹的個數(shù)

rosefunR 2019-07-23 10:56:40 ?8639 ?收藏 17
分類專欄： LeetCode
版權(quán)
1.問題
先序序列（前序序列）為a,b,c,d 的不同二叉樹的個數(shù)是?

2.解決思路
已知，前序序列和中序序列可以唯一地確定一棵二叉樹。如果我們把前序序列看作為入棧次序，把中序序列看作為出棧次序，那么題意相當于“以序列 a,b,c,d 為入棧次序，則出棧序列的個數(shù)為？”

比如：

? ?a ? ? ? ? ? ?
?/ ? \
b ? ?d ? ? ? ??
?\ ? ??
? c ? ? ? ? ? ?
1
2
3
4
5
前序遍歷：（父左右）a bc d
中序遍歷：（左父右）bc a d

由前序遍歷，a 是父節(jié)點；那么，由中序遍歷， bc 就是左子樹； d是右子樹；
由前序遍歷，b是父節(jié)點；那么，由中序遍歷， c 就是右子樹；
得到的二叉樹是唯一的。

因此，這個二叉樹可以由以下的前序序列和中序序列確定：

前序序列，先壓入 ab; 壓出的 b 當做中序序列；再壓入 c, 再壓出 c, 再壓出 a ；再壓入 d, 再壓出 d .

卡特蘭數(shù)

一個棧(無窮大)的進棧序列為1，2，3，…，n，有多少個不同的出棧序列?

f ( n ) = C 2 n n ? C 2 n n ? 1 f(n) = C_{2n}^{n} - C_{2n}^{n-1}
f(n)=C?
2n
n
??? ?
??C?
2n
n?1
??? ?
?

如何單純按照先序序列來看的話，就是，把序列的每個點看作一個根節(jié)點，就相當于左子樹和右子樹可能個數(shù)兩部分相乘。

因此，本題的答案是 14。
————————————————
版權(quán)聲明：本文為CSDN博主「rosefunR」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/rosefun96/article/details/96974507

總結(jié)

以上是生活随笔為你收集整理的【二叉树】先序序列为a,b,c,d 的不同二叉树的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。