這篇總結主要介紹樹中比較常見的一類題型–樹的構造。其實本質還是用遞迴的手法來實現，但是這類題目有一個特點，就是它是構建一棵樹，而不是給定一棵樹，然後進行遍歷，所以實現起來思路上有點逆向，還是要練習一下。LeetCode中關於樹的構造的題目有以下幾道：
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree
Construct Binary Tree from Preorder and Inorder Traversal
先來看看最簡單的Convert Sorted Array to Binary Search Tree，陣列本身是有序的，那麼我們知道每次只要取中點作為根，然後遞迴構建對應的左右子樹就可以了，遞迴的寫法跟常規稍有不同，就是要把根root先new出來，然後它的左節點接到遞迴左邊部分的返回值，右節點接到遞迴右邊部分的返回值，最後將root返回回去。這個模板在樹的構造中非常有用，其他幾道題也都是按照這個來實現。
接下來是Convert Sorted List to Binary Search Tree，這個跟Convert Sorted Array to Binary Search Tree比較近似，區別是元素儲存的資料結構換成了連結串列，不過引入了一個重要的問題，就是連結串列的訪問不是隨機存取的，也就是不是O(1)的，如果每次去獲取中點，然後進行左右遞迴的話，我們知道得到中點是O(n/2)=O(n)的，如此遞推式是T(n) = 2T(n/2) n/2，複雜度是O(nlogn)，並不是線性的，所以這裡我們就得利用到樹的中序遍歷了，按照遞迴中序遍歷的順序對連結串列結點一個個進行訪問，而我們要構造的二分查詢樹正是按照連結串列的順序來的。如此就能按照連結串列的訪問順序來構造，不會因此而增加找中間結點的複雜度。
最後是Construct Binary Tree from Preorder and Inorder Traversal和Construct Binary Tree from Inorder and Postorder Traversal，這個方法還是跟上面的題目一樣來構造，主要問題是如何將節點劈成左右兩部分進行遞迴，Construct Binary Tree from Preorder and Inorder Traversal就是利用前序遍歷跟一定在第一個，而中序遍歷又可以根據根來把元素劈成兩塊，類似的Construct Binary Tree from Inorder and Postorder Traversal是根據後序遍歷最後一個是根的特點，然後利用中序遍歷劈塊，原理是一樣的，最後的實現大家可以參考一下程式碼。
這篇總結主要介紹了LeetCode中四個樹的構造的題目，比較統一的思路就是在遞迴中建立根節點，然後找到將元素劈成左右子樹的方法，遞迴得到左右根節點接上建立的根然後返回。方法還是比較具有模板型的，不熟悉的朋友可以練習一下哈。