假設入棧操作由正數表示出棧操作由負數表示正數和負數都看作一個符號在每一組人棧和出棧序列前加一個符號O將該串稱為前置符號O的入棧和出棧序列(文中簡稱前置O棧序列)該序列構成n+ 個符號的串把該串看作一棵二叉樹的前序遍歷序列如圖所示當n為時僅有一種前置O棧序列O+O表示棧底+表示入棧表示出棧對應的二叉樹如圖 (a)所示在圖 (a)的某個葉子結點上增加一對左右孩子則形成圖 (b)的兩棵樹正好對應n=時的兩種前置O棧序列圖(b)的第一棵樹的前序遍歷為O++其意義是O棧底入棧入棧出棧l出棧同理圖(b)的第棵樹的前序遍歷為O++分別表示O棧底入棧 l出棧入棧出棧在圖l(b)任一棵樹的任一葉子結點上增加一對左右孩子 則構成一棵新的二叉樹新產生的樹共有棵在這棵樹中有兩棵樹同構（兩棵樹具有相同的形
狀）所以當n=時共有種出棧序列
前置O棧序列對應的二叉樹具有以下性質
[] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22745.html
