web开发 微服务 劝酒文化 post ftp vue开发文档 后台模板下载 jq点击事件 jquery点击事件 jquery去除空格 centos查看php版本 mysql小数用什么类型 js基本数据类型有哪些 svn安装后右键不显示 python实例 mysql查询 python如何实现多线程 python自定义异常 javasocket通信 java的方法 asp建站系统 microkms 路由器辐射大吗 免费脚本 pr黑场过渡 backtrack3 按键精灵脚本教程 视频修复工具 深渊碎片 视频编辑专家下载 js字符转数字 mysql导出数据 免费图片文字识别软件 发射爱心的图片 linux系统下载 sql2008r2 bootskin EarthView 类似迅雷的下载软件 红巨星插件
当前位置: 首页 > 学习教程  > 编程语言

力扣题解-106. 从中序与后序遍历序列构造二叉树(分治法思想,递归的方式求解)

2020/12/5 9:37:59 文章标签:

题目:106. 从中序与后序遍历序列构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder [9,3,15,20,7] 后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树: 3/ \…

题目:106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

后序遍历序列的最后一个元素即为根节点。

中序遍历序列的根节点位于中间,左边为其左子树构成的中序遍历序列,右边为其右子树构成的中序遍历序列。

根据左右子树的序列长度,就可以确定后序遍历序列的左右子树序列的分界点。

举例来说明分治法思想的运用。

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

  1. divide
    首先找出根节点,即postorder的元素3;然后找到元素3在inorder的位置,将inorder序列分为左子树序列 [9] 和右子树序列 [15,20,7];

此时根据inorder的左子树序列可以确定,将postorder分为左子树序列 [9] 和右子树序列 [15,7,20];

  1. conquer
    构造根节点root(3),然后递归地处理左子树序列和右子树序列,分别作为左子树left和右子树right。

  2. combine
    将二叉树拼接起来,即root->left = left,root->right = right, 返回root。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<int> inorder;
    vector<int> postorder;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->inorder = inorder;
        this->postorder = postorder;
        return dfs(0, inorder.size()-1, 0, postorder.size()-1);
    }

    TreeNode* dfs(int startIn, int endIn, int startPost, int endPost) {
        if (startPost > endPost or startIn > endIn) {
            return NULL;
        }

        if (startPost == endPost or startIn == endIn) {
            return new TreeNode(postorder[startPost]);
        }

        TreeNode * root = new TreeNode(postorder[endPost]);

        int rootPos = findRootPosInorder(postorder[endPost], startIn, endIn);
        if (rootPos < 0) {
            return NULL;
        }
        int leftStartIn = startIn;
        int leftEndIn = rootPos-1;
        int rightStartIn = rootPos+1;
        int rightEndIn = endIn;

        int leftSize = rootPos-startIn;

        int leftStartPost = startPost;
        int leftEndPost = startPost + leftSize-1;
        int rightStartPost = startPost + leftSize;
        int rightEndPost = endPost-1;

        root->left = dfs(leftStartIn, leftEndIn, leftStartPost, leftEndPost);
        root->right = dfs(rightStartIn, rightEndIn, rightStartPost, rightEndPost);

        return root;
    }

    int findRootPosInorder(int value, int startIn, int endIn) {
        for (int i = startIn; i <= endIn; i++) {
            if (value == inorder[i]) {
                return i;
            }
        }
        return -1;
    }
};

本文链接: http://www.dtmao.cc/news_show_450036.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?