二叉樹 中序周遊 python_刷leetcode——從前序與中序周遊序列構造二叉樹

原題

根據一棵樹的前序周遊與中序周遊構造二叉樹。

注意:你可以假設樹中沒有重複的元素。

例如，給出

前序周遊 preorder = [3,9,20,15,7]中序周遊 inorder = [9,3,15,20,7]
           

傳回如下的二叉樹：

3   /   9  20            /          15   7
           

原題url：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解題

這道題目，主要就是在于大家對于二叉樹這個資料結構的熟悉程度了，根據其前序周遊和中序周遊，推算出原本的二叉樹。

我們想想，如果不是寫代碼，隻是通過手寫的話，我們是如何查找的，就用題目給出的例子：

1. 根據前序周遊，第一個一定是根節點，那麼 3 就是根節點。
2. 從中序周遊中尋找 3，在它左邊的，都是其左子樹上的節點，在它右邊的，都是其右子樹上的節點。
3. 因為中序周遊中，3 的左邊隻有9，那麼 9 就是 3 的左子節點。
4. 根據前序周遊先根然後左子節點，然後再右子節點的規律，3 、9 之後的 20 一定是 3 的右子節點。
5. 20 在中序周遊中，其左右兩邊就是 15 和 7，是以15 和 7 就分别是它的左右子節點。

根據上面的分析，你就可以畫出例子中的二叉樹了。

那麼我們尋找的順序是，先從前序周遊的第一個節點開始，在中序周遊中找出它的位置，其左右兩邊就是其左右子樹了，

接着從左子樹入手，前序周遊根節點之後的兩個節點應該就是其左右子樹，但需要考慮沒有左右子樹的情況，然後再以其子樹為根，在中序周遊中找其左右子樹。

需要注意的是，隻有針對根節點，其左右子節點是在前序周遊中緊跟着根節點的，其他都是有距離的，需要根據左子樹遞推。

接下來看看代碼：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    int[] preorder;    int[] inorder;    // preorder中周遊過的數量，這樣找完左子樹中的節點，剩下的第一個節點，必然是右子節點    int preorderIndex = 0;    // key為inorder中的值，value為inorder中的下标    Map inorderMap;    public TreeNode buildTree(int[] preorder, int[] inorder) {        if (preorder.length == 0) {            return null;        }        TreeNode node = new TreeNode(preorder[0]);        if (preorder.length == 1) {            return node;        }        this.preorder = preorder;        this.inorder = inorder;        this.inorderMap = new HashMap<>(inorder.length * 4 / 3 + 1);        for (int i = 0; i < inorder.length; i++) {            this.inorderMap.put(inorder[i], i);        }        return generateNode(0, inorder.length);    }    /**     * 尋找目前節點的左右子節點     * start：inorder裡開始尋找的節點下标     * end：inorder裡終止尋找的節點下标     * preorderIndex：目前節點在preorder中的下标     */    public TreeNode generateNode(int start, int end) {        if (start >= end) {            return null;        }        // 目前節點        int value = preorder[preorderIndex];        TreeNode node = new TreeNode(value);        // 目前節點的值，在inorder中的下标        int inorderIndex = inorderMap.get(value);        // 目前節點已經找到，尋找下一個節點。        // 因為會先去尋找左節點，當該節點左子樹中所有節點全部找完後，前序周遊中，剩下節點的第一個節點，一定是該節點的右節點。        preorderIndex++;        // 尋找左節點        node.left = generateNode(start, inorderIndex);        // 尋找右節點        node.right = generateNode(inorderIndex + 1, end);        return node;    }}
           

送出OK，執行用時：3 ms，記憶體消耗：40.1 MB。

總結

以上就是這道題目我的解答過程了，不知道大家是否了解了。這道題目主要就是尋找規律，優化的話，可能就是利用 map 構造中序周遊中節點值和順序的關系。

有興趣的話可以通路我的部落格或者關注我的公衆号、頭條号，說不定會有意外的驚喜。

https://death00.github.io/

公衆号：健程之道