106、從中序與后序遍歷序列構造二叉樹(shù)

admin2024-06-21  13

給定兩個(gè)整數數組?inorder?和?postorder?,其中?inorder?是二叉樹(shù)的中序遍歷,?postorder?是同一棵樹(shù)的后序遍歷,請你構造并返回這顆?二叉樹(shù)?。

106、從中序與后序遍歷序列構造二叉樹(shù),第1張

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder?和?postorder?都由?不同?的值組成
  • postorder?中每一個(gè)值都在?inorder?中
  • inorder?保證是樹(shù)的中序遍歷
  • postorder?保證是樹(shù)的后序遍歷

題解:要充分理解中序和后序的概念,后序的最后一個(gè)值就是根節點(diǎn)的值,由此找到根節點(diǎn),再根據這個(gè)信息去分割中序數組,可以將中序數組分割為左中序和右中序,分割完成后左中序、右中序數組的大小就確定了。用這個(gè)大小也就可以去分割后序數組(注意是將后序最后一個(gè)元素去掉后分割,也就是將根節點(diǎn)剔除),同樣后序數組也可以分割為左后序,右后序。這樣將左中序、左后序組合,右中序,右后序組合進(jìn)行遞歸,每次遞歸返回一個(gè)root節點(diǎn),也就是最后會(huì )返回二叉樹(shù)的根節點(diǎn),完成整個(gè)二叉樹(shù)的構建。

代碼如下:

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        // 后序遍歷數組最后一個(gè)元素,就是當前的中間節點(diǎn)
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // 葉子節點(diǎn)
        if (postorder.size() == 1) return root;

        // 找到中序遍歷的切割點(diǎn)
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }

        // 切割中序數組
        // 左閉右開(kāi)區間:[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

        // postorder 舍棄末尾元素
        postorder.resize(postorder.size() - 1);

        // 切割后序數組
        // 依然左閉右開(kāi),注意這里使用了左中序數組大小作為切割點(diǎn)
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

注意:

1、對于這句代碼的解釋

vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
  • 向量聲明和初始化vector<int> leftInorder 聲明了一個(gè)新的整型向量(vector<int>),名稱(chēng)為 leftInorder。

  • 構造函數(inorder.begin(), inorder.begin() + delimiterIndex) 是向量的構造函數,用于指定新向量的初始化方式。這里使用的是范圍構造函數,它可以從另一個(gè)向量的一部分元素來(lái)創(chuàng )建新向量。

  • 迭代器范圍

    • inorder.begin() 返回指向 inorder 向量第一個(gè)元素的迭代器。
    • inorder.begin() + delimiterIndex 返回指向 inorder 向量中從第一個(gè)元素起偏移 delimiterIndex 個(gè)位置的迭代器。注意,這個(gè)位置不包括在新向量中。
  • 范圍含義inorder.begin()inorder.begin() + delimiterIndex 之間的元素(包括起始位置的元素,不包括結束位置的元素)將被復制到新向量 leftInorder 中。

2、

前序和中序可以唯一確定一棵二叉樹(shù)。

后序和中序可以唯一確定一棵二叉樹(shù)。

那么前序和后序可不可以唯一確定一棵二叉樹(shù)呢?

前序和后序不能唯一確定一棵二叉樹(shù)!,因為沒(méi)有中序遍歷無(wú)法確定左右部分,也就是無(wú)法分割。

本文來(lái)自互聯(lián)網(wǎng)用戶(hù)投稿,該文觀(guān)點(diǎn)僅代表作者本人,不代表本站立場(chǎng)。本站僅提供信息存儲空間服務(wù),不擁有所有權,不承擔相關(guān)法律責任。如若轉載,請注明原文出處。如若內容造成侵權/違法違規/事實(shí)不符,請聯(lián)系SD編程學(xué)習網(wǎng):675289112@qq.com進(jìn)行投訴反饋,一經(jīng)查實(shí),立即刪除!
一级毛片在线一区二区-亚洲精品无码专区土豆网在线播放-亚洲无乱码一区二区三区-亚洲一区二区三区精品