這篇總結主要介紹樹中比較常見的一類題型–樹的構造。其實本質還是用遞迴的手法來實現,但是這類題目有一個特點,就是它是構建一棵樹,而不是給定一棵樹,然後進行遍歷,所以實現起來思路上有點逆向,還是要練習一下。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中四個樹的構造的題目,比較統一的思路就是在遞迴中建立根節點,然後找到將元素劈成左右子樹的方法,遞迴得到左右根節點接上建立的根然後返回。方法還是比較具有模板型的,不熟悉的朋友可以練習一下哈。
写评论
很抱歉,必須登入網站才能發佈留言。