1. Toy模板网首页
  2. > Toy博客

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序

9月前 作者：LuckyRich1 分类：Toy博客 阅读(31) 违法举报

这篇具有很好参考价值的文章主要介绍了【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例
【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

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

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

解题思路及实现

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

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]);

        //找到根的左右子树区间
         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. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

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]);

        //找到根的左右子树区间
         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. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

解题思路及实现

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

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. 二叉树的前序遍历非递归实现

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

解题思路及实现

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur=root;
        while(cur || !st.empty())
        {
            //左路结点一直进栈
            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. 二叉树的中序遍历非递归实现

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

解题思路及实现

中序非递归和前序非递归代码几乎一样，可以自己尝试画图分析一波。

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. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

145. 二叉树的后序遍历非递归实现

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展

解题思路及实现

【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序,LeetCood,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/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右子树为空，或者右子树不为空且右子树被访问过了(上一个被访问的结点时右子树的根)
            //那就说明右子树不用访问或者被访问过了，直接访问根top
            //2.右子树不为空，且没有被访问，则迭代子问题访问
            if(top->right == nullptr || top->right == prev)
            {
                v.push_back(top->val);
                st.pop();
                prev=top;
            }
            else
            {
                cur=top->right;             
            }

        }
        return v;
    }
};

到了这里，关于【LeetCode】105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树，144. 二叉树的前序遍历非递归实现，94. 二叉树的中序遍历非递归实现，145. 二叉树的后序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包