[ inorder postorder construct tree ] 用中序、後序建樹保證$\ord{N}$的方法

昨天我學長因為要面試，所以努力地刷leetcode的題目，寫到了一題:

• 106. Construct Binary Tree from Inorder and Postorder Traversal  

他雖然AC了但是用的方法不太好，因此跑來問我有沒有看起來很帥速度又快的方法。

因為網路上的code都用一些很慢的方法來建樹，很多都$\ord{N^2}$，雖然也有看似$\ord{N}$的方法，但是用到像是unordered_map之類常數很大也不保證複雜度是$\ord{1}$(codeforces會卡內建hash)。

因為我查到的code都太糟糕了，因此我決定自己寫一個複雜度保證為$\ord{N}$又好寫的方法。

首先是找$root$的部分，因為有給後序的關係很容易就是到是誰了，但是找左右子樹就會出問題。經過觀察，只需要在dfs的過程用stack紀錄一些特別點就可以好好地維護左右子樹。

假設現在dfs在點$u$，stack紀錄的點就是從$root$到$u$的路徑所有點中，除了那些左小孩也在該路徑中的點之外的所有點，有點複雜看個圖會比較明白，紅色的點就是記錄在stack中的點。

至於為什麼記錄這些點就可以在dfs時判斷現在是不是NULL的節點，以及如果給的是preorder的情況就交給讀者思考了
以下附上程式碼:

	class Solution{
	int i,j;
	stack<int,vector<int>> st;
	const vector<int> *in,*po;
	TreeNode *dfs(){
	if(j==-1||(st.size()&&st.top()==in->at(i)))return 0;
	st.emplace(po->at(j));
	TreeNode *o=new TreeNode(po->at(j--));
	o->right=dfs();
	st.pop(),--i;
	o->left=dfs();
	return o;
	}
	public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
	i=j=int(inorder.size())-1;
	stack<int,vector<int>>().swap(st);
	in=&inorder,po=&postorder;
	return dfs();
	}
	};

view raw construct_tree.cpp hosted with ❤ by GitHub