国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序

2年前作者：LuckyRich1分類：Toy博客閱讀(27)違法舉報(bào)

這篇具有很好參考價值的文章主要介紹了【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

105. 從前序與中序遍歷序列構(gòu)造二叉樹

給定兩個整數(shù)數(shù)組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點(diǎn)。

示例
【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
輸出: [3,9,20,null,null,15,7]

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

解題思路及實(shí)現(xiàn)

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

class Solution {
public:
    //prei必須是一個引用，不然遞歸返回的prei還是上一層的prei
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend)
     {
        //缺少了遞歸返回條件，下面分析一下
        
         TreeNode* root=new TreeNode(preorder[prei]);

        //找到根的左右子樹區(qū)間
         int rooti=inbegin;//根是會變得，因此不能賦值為0
         while(rooti <= inend)
         {
             if(inorder[rooti] == preorder[prei])
                break;

            ++rooti;
         }

        //遞歸下一層之前都要向前+1找根
        ++prei;

        //[inbegin rooti-1] rooti [rooti inend]
        root->left=_buildTree(preorder,inorder,prei,inbegin,rooti-1);
        root->right=_buildTree(preorder,inorder,prei,rooti+1,inend);
        return root;
     }


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {       
        int prev=0;
        return _buildTree(preorder,inorder,prev,0,inorder.size()-1);

    }
};

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

class Solution {
public:
    //prei必須是一個引用，不然遞歸返回的prei還是上一層的prei
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend)
     {
        if(inbegin > inend)
            return nullptr;
            
         TreeNode* root=new TreeNode(preorder[prei]);

        //找到根的左右子樹區(qū)間
         int rooti=inbegin;//根是會變得，因此不能賦值為0
         while(rooti <= inend)
         {
             if(inorder[rooti] == preorder[prei])
                break;

            ++rooti;
         }

        //遞歸下一層之前都要向前+1找根
        ++prei;

        //[inbegin rooti-1] rooti [rooti inend]
        root->left=_buildTree(preorder,inorder,prei,inbegin,rooti-1);
        root->right=_buildTree(preorder,inorder,prei,rooti+1,inend);
        return root;
     }


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {       
        int prev=0;
        return _buildTree(preorder,inorder,prev,0,inorder.size()-1);

    }
};

106. 從中序與后序遍歷序列構(gòu)造二叉樹

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

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

解題思路及實(shí)現(xiàn)

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int inbegin,int inend,int& posti) {

        if(inbegin > inend)
            return nullptr;
        
        TreeNode* root=new TreeNode(postorder[posti]);

        int rooti=inbegin;
        while(rooti <= inend)
        {
            if(inorder[rooti] == postorder[posti])
                break;
            
            ++rooti;
        }

        --posti;
        root->right=_buildTree(inorder,postorder,rooti+1,inend,posti);
        root->left=_buildTree(inorder,postorder,inbegin,rooti-1,posti);
        return root;
    
         
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int post=postorder.size()-1;
        return _buildTree(inorder,postorder,0,inorder.size()-1,post);
    }
};

144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)

給你二叉樹的根節(jié)點(diǎn) root ，返回它節(jié)點(diǎn)值的 前序 遍歷。
【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

解題思路及實(shí)現(xiàn)

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur=root;
        while(cur || !st.empty())
        {
            //左路結(jié)點(diǎn)一直進(jìn)棧
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }

            //出棧，訪問它的右子樹
            TreeNode* top=st.top();
            st.pop();
            cur=top->right;
        }

        return v;

    }
};

94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)

給定一個二叉樹的根節(jié)點(diǎn) root ，返回 它的 中序 遍歷 。
【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

解題思路及實(shí)現(xiàn)

中序非遞歸和前序非遞歸代碼幾乎一樣，可以自己嘗試畫圖分析一波。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode* cur=root;

        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            TreeNode* top=st.top();
            st.pop();
            v.push_back(top->val);

            cur=top->right;
        }
        return v;
    }
};

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

145. 二叉樹的后序遍歷非遞歸實(shí)現(xiàn)

給你一棵二叉樹的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值的 后序遍歷 。
【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展

解題思路及實(shí)現(xiàn)

【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序,LeetCood,leetcode,算法,職場和發(fā)展文章來源地址http://www.zghlxwxcb.cn/news/detail-758685.html

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur=root;
        TreeNode* prev=nullptr;
        while(cur || !st.empty())
        {

            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            TreeNode* top=st.top();
            //1.top右子樹為空，或者右子樹不為空且右子樹被訪問過了(上一個被訪問的結(jié)點(diǎn)時右子樹的根)
            //那就說明右子樹不用訪問或者被訪問過了，直接訪問根top
            //2.右子樹不為空，且沒有被訪問，則迭代子問題訪問
            if(top->right == nullptr || top->right == prev)
            {
                v.push_back(top->val);
                st.pop();
                prev=top;
            }
            else
            {
                cur=top->right;             
            }

        }
        return v;
    }
};

到了這里，關(guān)于【LeetCode】105. 從前序與中序遍歷序列構(gòu)造二叉樹，106. 從中序與后序遍歷序列構(gòu)造二叉樹，144. 二叉樹的前序遍歷非遞歸實(shí)現(xiàn)，94. 二叉樹的中序遍歷非遞歸實(shí)現(xiàn)，145. 二叉樹的后序的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包