# Counting Binary Tree

最近演算法剛學到DP，其中一個問題是如何有效率的執行矩陣乘法
如果使用暴力解，那可以執行的乘法順序將會和catalan number相同

讓我想起了Data Structure有學到的東西
這題和給定1,...,n個node，有幾種可能的binary tree是相同的

給定一個數列1,...,n的infix/postfix或者infix/prefix表示法
可以唯一決定一顆binary tree，事實上每個infix都對應到唯一的binary tree，延伸的問題是，給一個postfix或prefix，他們可能對應到的binary tree有幾種
解法有數種，其中最直觀就是使用DFS
將prefix(or postfix)丟入stack中看能產生幾種permutation
DFS執行之可能順序即是infix的可能，記得inorder就是LVR

以下是DFS的程式碼

#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <stack>
#include <queue>
using namespace std;

const int Size=3;
stack<int> s;

inline void DFS(int* a,int index,queue<int> result) {
	
	if (result.size() == Size) {
		while (!result.empty()) {
			cout << result.front() << " ";
			result.pop();
		}
		cout << endl;
		return;
	}
	
	if (index >= 0) {
		s.push(a[index]);
		index--;
		DFS(a, index,result);
		s.pop();
		index++;
	}

	if (!s.empty()) {
		int tmp = s.top();
		result.push(s.top());
		s.pop();
		DFS(a, index,result);
		result.pop();
		s.push(tmp);
	}

}

int main(void) {
	
	int a[Size] = { 3,2,1 };
	while (!s.empty())
		s.pop();
	queue<int> q;
	while (!q.empty())
		q.pop();
	DFS(a, 2,q);


	return 0;
}

輸入1,2,3，可能產生的infix順序有幾種
另一個是用DP的方式執行

$F(n)=\sum_{i=0}^{n-1}F(i)*F(n-i)$