周遊序列構造二叉樹總結

從中序與後序周遊序列構造二叉樹

題目

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

注意:

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

例如，給出

中序周遊 inorder = [9,3,15,20,7]
後序周遊 postorder = [9,15,7,20,3]      

傳回如下的二叉樹：

3
   / \
  9  20
    /  \
   15   7      

解題思路

根據題意, 我們知道後序周遊的形式是先周遊左子樹點，然後是右子樹，最後是根節點；中序周遊的形式是，先左子樹，再根節點，最後是右節點；

隻要我們在中序周遊中定位到根節點，那麼我們就可以分别知道左子樹和右子樹中的節點數目。我們可以發現後序周遊的數組最後一個元素代表的即為根節點，由于同一顆子樹的後序周遊和中序周遊的長度顯然是相同的，是以我們就可以對應到後序周遊的結果中，對上述形式中的所有左右括号進行定位。

這樣以來，我們就知道了左子樹的後序周遊和中序周遊結果，以及右子樹的後序周遊和中序周遊結果，我們就可以遞歸地對構造出左子樹和右子樹，再将這兩顆子樹接到根節點的左右位置。

在中序周遊中對根節點進行定位時，我們可以考慮使用哈希表來幫助我們快速地定位根節點。對于哈希映射中的每個鍵值對，鍵表示一個元素（節點的值），值表示其在中序周遊中的出現位置，代碼實作如下：

代碼實作

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 定義哈希表用于定位中序數組根節點的的位置
    public HashMap<Integer, Integer> map = new HashMap();
    int[] post;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        post = postorder;
        TreeNode root = helper(0, inorder.length - 1, 0, post.length - 1);
        return root;
    }

        public TreeNode helper(int inStart, int inEnd, int postStart, int{
        if (inStart > inEnd || postStart > postEnd) return null;
        int val = post[postEnd];
        int rootPos = map.get(val);
        TreeNode node = new TreeNode(val);
        node.left = helper(inStart, rootPos -1 , postStart, postStart + rootPos - inStart -1);
        node.right = helper(rootPos+1, inEnd, postStart + rootPos - inStart, postEnd - 1);
        return      

複雜度分析：

• 時間複雜度：O(n)，其中 n 是樹中的節點個數。
• 空間複雜度：O(n)。我們需要使用 O(n) 的空間存儲哈希表，以及 O(h)（其中 h 是樹的高度）的空間表示遞歸時棧空間。這裡 h < n，是以總空間複雜度為 O(n)。

從前序與中序周遊序列構造二叉樹

題目

給定一棵樹的前序周遊 preorder 與中序周遊 inorder。請構造二叉樹并傳回其根節點。

解題思路

根據題意, 我們知道前序周遊的形式是先周遊根節點，然後是左子樹，最後是右子樹；中序周遊的形式是，先左子樹，再根節點，最後是右節點；

隻要我們在中序周遊中定位到根節點，那麼我們就可以分别知道左子樹和右子樹中的節點數目。由于同一顆子樹的前序周遊和中序周遊的長度顯然是相同的，是以我們就可以對應到前序周遊的結果中，對上述形式中的所有左右括号進行定位。

代碼實作

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public HashMap<Integer, Integer> map = new HashMap();
    int[] preOrder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.preOrder = preorder;

        return helper(0, inorder.length - 1, 0, preOrder.length - 1);
    }

    public TreeNode helper(int inStart, int inEnd, int preStart, int preEnd) {
        if (inStart > inEnd || preStart > preEnd) return null;
        int root = preOrder[preStart]; 
        int pos = map.get(root);
        TreeNode node = new TreeNode(root);
        node.left = helper(inStart, pos - 1, preStart + 1, preStart + pos - inStart);
        node.right = helper(pos + 1, inEnd, preStart + pos - inStart + 1, preEnd);
        return node;      

複雜度分析

• 時間複雜度：O(n)，其中 n 是樹中的節點個數。
• 空間複雜度：O(n)，除去傳回的答案需要的 O(n) 空間之外，我們還需要使用 O(n) 的空間存儲哈希映射，以及 O(h)（其中 h 是樹的高度）的空間表示遞歸時棧空間。這裡 h < n，是以總空間複雜度為 O(n)。