卡特兰数和括号匹配

虽然卡特兰数的程序的写出比较容易记忆，卡特兰数和括号匹配我一直想不清楚之间的关系。

都知道卡特兰数是C3 = C2xC0+C1xC1 + C0xC2但是对于

已知

C1是()

C2是()()和(())

对于C3来说，
()()()
((()))
(())()
()(())
(()())
哪一个才是C2xC0，哪个才是C1xC1, C0xC2一直很混淆。尤其是上面的五种并不是左右对称。

今天终于有时间思考了一下。分享心得。抛砖引玉。看有什么更好的符合直觉的思路。

1. 
   
2. 
   
3.         空        空           空           空           空
   
4.       (   )     (   )       (    )       (    )       (   )
   
5.     (   )     (   )       (   )(   )        (   )       (   )
   
6.   (   )         (   )                     (   )           (   )
   
7.   ————————————————————————————————————————————————————————————
   
8.   规则是如果左括号表示嵌套关系，右括号表示跟随的关系。
   
9.   ((()))      (()())      (())()        ()(())        ()()()
   
10. 
    

复制代码

举例为什么左二是(()())。第一个（是第一层的左孩子。因为是左孩子，所以要嵌套（不出栈）。这样有了(()。因为第二层是右孩子所以要跟随。变成(()()，加上第一层的无孩子的右孩子，变成结果(()())。