Əvvəlcədən Sifariş və Sifarişdən Sonra Traversal LeetCode Həllindən Binar Ağac qurun

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Bloomberg google ÜberBaxılıb 17

Problem bəyanat

Əvvəlcədən Sifarişdən və Sifarişdən Sonra Traversal LeetCode Həllindən Binar Ağacı qurun - İki tam massiv nəzərə alınmaqla, preorder və postorder hara preorder dır,-dir,-dur,-dür əvvəlcədən sifariş ikili ağacının fərqli dəyərlər və postorder dır,-dir,-dur,-dür sifarişdən sonra traversal eyni ağac, yenidən qurmaq və geri qaytarmaq bu ikili ağac.

Bir neçə cavab varsa, edə bilərsiniz istənilən birini qaytarın onlardan.

Əvvəlcədən Sifariş və Sifarişdən Sonra Traversal LeetCode Həllindən Binar Ağac qurunPin

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Izahat

Biz bilirik ki, pre massivdə ilk element kökdür. Biz həmçinin bilirik ki, premassivdəki ikinci element sol alt ağacın köküdür. İndi bu ikinci elementi post massivində tapa bilsək, ondan əvvəlki bütün elementlər və o daxil olmaqla sol alt ağaca aid olacaq və ondan sonrakı bütün elementlər (kök olan sonuncu element istisna olmaqla) sağ alt ağacdakı elementlər olacaq. Əvvəlcədən massivdəki hər bir elementi emal edərkən və ağacı qurarkən bu məntiqi rekursiv şəkildə tətbiq edə bilərik. Biz post massivində sürətli axtarışlar üçün hashmap istifadə edirik.

İstifadə edərək onu alt problemlərə endirsək, problemi həll etmək daha asandır Bölün və fəth edin.

Əvvəlcədən sifariş: 1 2 4 5 3 6 və sonrakı sifariş: 4 5 2 6 3 1

Bunu belə görə bilərik: 1 ( 2 4 5) ( 3 6 ) və ( 4 5 2 ) ( 6 3 ) 1

Əvvəlcədən Sifariş və Sifarişdən Sonra Traversal LeetCode Həllindən Binar Ağac qurunPin

Kodu

Əvvəlcədən sifarişdən və sifarişdən sonrakı keçiddən binar ağacın qurulması üçün C++ kodu

#define null nullptr
class Solution {
public:
    int i = 0;
    TreeNode* help(vector<int>& pre, vector<int>& post,int start,int end){
        //BAse Case
        if(start>end) return null;
        if(i>=pre.size()) return null;
        int j =-1;
        for(int k = start;k<=end;k++)
            if(pre[i]==post[k]){
                j=k;
                break;
            }
        if(j==-1) return null;
        i++;
        TreeNode* root = new TreeNode(post[j]);
        TreeNode* l = help(pre,post,start,j-1);
        root->left=l;
        TreeNode* r = help(pre,post,start,j-1);
        root->right=r;
        return root;
    }
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return help(pre,post,0,post.size()-1);
    }
};

Əvvəlcədən və sifarişdən sonrakı keçiddən binar ağacın qurulması üçün Python kodu

class Solution:
    def constructFromPrePost(self, pre, post):
        return self.constructFromPrePostRecurUtil(
            pre, 0, len(pre) - 1, post, 0, len(post) - 1)
        
    def constructFromPrePostRecurUtil(
            self, 
            pre, 
            preStart, 
            preEnd, 
            post, 
            postStart, 
            postEnd):
        # Base case.
        if (preStart > preEnd):
            return None
        if (preStart == preEnd):
            return TreeNode(pre[preStart])
        # Recursive case.
        root = TreeNode(pre[preStart])
        leftRootIndexInPre = preStart + 1
        leftRootIndexInPost = self.getIndexInPost(
            post, pre[leftRootIndexInPre])
        leftEndIndexInPre = leftRootIndexInPre + \
            (leftRootIndexInPost - postStart)
        root.left = self.constructFromPrePostRecurUtil(
            pre, 
            leftRootIndexInPre, 
            leftEndIndexInPre, 
            post, 
            postStart, 
            leftRootIndexInPost)
        root.right = self.constructFromPrePostRecurUtil(
            pre, 
            leftEndIndexInPre + 1, 
            preEnd, 
            post, 
            leftRootIndexInPost + 1, 
            postEnd - 1)
        return root
        
    def getIndexInPost(self, post, target):
        for i, v in enumerate(post):
            if v == target:
                return i
        return -1   # to optimize

Əvvəlcədən və sifarişdən sonrakı keçiddən binar ağacın qurulması üçün Java kodu

class Solution {
    public TreeNode helper(int[] pre,int[] post,int psi,int pei,int ppsi,int ppei ) {
        if (psi>pei) return null;
        TreeNode root=new TreeNode(pre[psi]);
        if(psi==pei) return root;
        int idx=ppsi;
        while(post[idx]!=pre[psi+1]){idx++;}
        int tne=idx-ppsi+1;
        root.left=helper(pre,post,psi+1,psi+tne,ppsi,idx);
        root.right=helper(pre,post,psi+tne+1,pei,idx+1,ppei-1);
        return root;
    }
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return helper(preorder,postorder,0,preorder.length-1,0,postorder.length-1);
    }
}

Əvvəlcədən sifarişdən və sifarişdən sonra keçiddən ikili ağacın qurulması üçün mürəkkəblik təhlili LeetCode Həll

Zamanın mürəkkəbliyi

O (nlogn)

Kosmik Mürəkkəblik

O (1)

Translate »