【剑指Offer】T7 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6},则重建二叉树并返回。

思路参考《王道数据结构》P120

思路:

  1. 由先序序列第一个pre[0] 在中序序列中找到根节点位置 gen
  2. gen 为中心遍历
    • 0~gen左子树

      • 子中序序列:0~gen-1,放入 vin_left[]
      • 子先序序列:1~gen 放入 pre_left[]+1 可以看图,因为头部有根节点
    • gen+1~vinlen为右子树
      • 子中序序列:gen+1 ~ vinlen-1 放入 vin_right[]
      • 子先序序列:gen+1 ~ vinlen-1 放入 pre_right[]
  3. 由先序序列 pre[0]创建根节点
  4. 连接左子树,按照左子树子序列递归(pre_left[]vin_left[]
  5. 连接右子树,按照右子树子序列递归(pre_right[]vin_right[]
  6. 返回根节点

1566200739629.png
1566200965090.png

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    int vinlen=vin.size();

    if(vinlen==0)
        return NULL;

    vector<int> pre_left, pre_right, vin_left, vin_right;

    //创建根节点,根节点肯定是前序遍历的第一个数
    TreeNode* head = new TreeNode(pre[0]);

    //找到中序遍历根节点所在位置,存放于变量gen中
    int gen=0;
    for(int i=0;i<vinlen;i++){
        if(vin[i]==pre[0]){
            gen=i;
            break;
        }
    }

    //对于中序遍历,根节点左边的节点位于二叉树的左边,根节点右边的节点位于二叉树的右边
    // 左子树
    for(int i = 0; i < gen; i++){
        vin_left.push_back(vin[i]);
        pre_left.push_back(pre[i+1]);//先序第一个为根节点
    }
    // 右子树
    for(int i = gen + 1; i < vinlen; i++){
        vin_right.push_back(vin[i]);
        pre_right.push_back(pre[i]);
    }
    //递归,执行上述步骤,区分子树的左、右子子树,直到叶节点
    head->left = reConstructBinaryTree(pre_left, vin_left);
    head->right = reConstructBinaryTree(pre_right, vin_right);
    return head;

}

leetcode T106 中序和后续构建二叉树

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    int len = postorder.size();
    if(len == 0)
        return NULL;

    // 在中序序列中找到根节点位置
    int gen = 0;
    for(gen = 0; gen < len, inorder[gen] != postorder[len-1]; gen++);

    vector<int> in_left, in_right, pos_left, pos_right;

    for(int i = 0; i < gen; i++){
        in_left.push_back(inorder[i]);
        pos_left.push_back(postorder[i]);
    }

    for(int i = gen+1; i < len; i++){
        in_right.push_back(inorder[i]);
        pos_right.push_back(postorder[i-1]);
    }

    TreeNode* head = new TreeNode(postorder[len-1]);
    head->left = buildTree(in_left, pos_left);
    head->right = buildTree(in_right, pos_right);

    return head;
}

本文链接:https://ariser.cn/index.php/archives/144/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!