首页 > 其他分享 >105. 从前序与中序遍历序列构造二叉树

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

时间:2024-12-10 14:09:59浏览次数:4  
标签:pre preorder index int root 中序 二叉树 inorder 105

问题描述

分析

逻辑上,从前序遍历中依次从前往后获取根结点,从中序里获取根结点的序号后可以获取左子树和右子树,递归构建树即可。

分治/递归

class Solution {
public:
    vector<int> preorder;
    vector<int> inorder;
    unordered_map<int, int> um;
    // 分治
    TreeNode* solve(int pre_l, int pre_r, int in_l, int in_r) {
        if (in_l > in_r || pre_l > pre_r) {
            return nullptr;
        }
        int root_index = um[preorder[pre_l]];
        TreeNode* root = new TreeNode();
        root->val = inorder[root_index];
        int n = root_index-in_l;
        root->left = solve(pre_l+1, pre_l+n+1, in_l, root_index-1);
        root->right = solve(pre_l+n+1, pre_r, root_index+1, in_r);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        this->inorder = inorder;
        for (int i = 0; i < inorder.size(); i++) {
            um[inorder[i]] = i; // 值为x的结点在中序遍历中是第i个
        }
        TreeNode* root;
        root = solve(0, preorder.size()-1, 0, inorder.size()-1);
        return root;
    }
};

拓展

事实上,solve的第二个参数pre_r可以更大,甚至可以去掉,因为每次递归只需找到该子树的前序遍历的第一个元素即可。

class Solution {
public:
    vector<int> preorder;
    vector<int> inorder;
    unordered_map<int, int> um;
    // 分治
    TreeNode* solve(int pre_l, int in_l, int in_r) {
        if (in_l > in_r) {
            return nullptr;
        }
        int root_index = um[preorder[pre_l]];
        TreeNode* root = new TreeNode();
        root->val = inorder[root_index];
        int n = root_index-in_l; // 左子树结点数量
        root->left = solve(pre_l+1, in_l, root_index-1);
        root->right = solve(pre_l+n+1, root_index+1, in_r);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        this->inorder = inorder;
        for (int i = 0; i < inorder.size(); i++) {
            um[inorder[i]] = i; // 值为x的结点在中序遍历中是第i个
        }
        TreeNode* root;
        root = solve(0, 0, inorder.size()-1);
        return root;
    }
};

该代码也能ac。

标签:pre,preorder,index,int,root,中序,二叉树,inorder,105
From: https://www.cnblogs.com/saulstavo/p/18597236

相关文章

  • LQ1050 杨辉三角
    题目描述杨辉三角又称作中国三角形11  11  2  11  3  3  11  4  6  4  11  5  10  10  5  11  6  15  20  15  6  11  7  21  35  35  21  7  1请在观察杨......
  • LCR 048. 二叉树的序列化与反序列化(困难)(主站297)
    https://leetcode.cn/problems/h54YBf/https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/难度:☆☆☆题目:序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另......
  • PAT 2024年春季 甲级 A-3 Degree of Skewness(二叉树的构建)
     给出后序和中序遍历序列,求出只有左子树和只有右子树的结点之差1#include<bits/stdc++.h>2usingnamespacestd;3intn;4intnl=0,nr=0;5structnode{6intdata,lchild=-1,rchild=-1;7};8vector<node>nodes(1005);9vector<int>in_o......
  • leetcode543.二叉树的直径
    给你一棵二叉树的根节点,返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。示例1:输入:root=[1,2,3,4,5]输出:3解释:3,取路径[4,2,1,3]或......
  • 学生大战期望题目¿h,艰难取胜。(UVA10529)
    /ll某事件\(A\)第一次发生的期望次数\(E(A)=\frac{1}{P(A)}\)。\(\color{Red}({1})\)所以设\(dp_i\)为连续放好\(i\)个的期望。显然有\(dp_0=0\)。由\(\color{Red}({1})\)得到有\(dp_1=\dfrac{1}{1-p_l-p_r}\)。所以同理对于一个骨牌不倒的期望次数为\(\dfra......
  • 114. 二叉树展开为链表
    问题描述给你二叉树的根结点root,请你将它展开为一个单链表:展开后的单链表应该同样使用TreeNode,其中right子指针指向链表中下一个结点,而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。分析注意,这里应该使用同样的TreeNode,也就是评判时,直接看原......
  • LCR 047. 二叉树剪枝(中等)(主站814)
    https://leetcode.cn/problems/pOCWxh/https://leetcode.cn/problems/binary-tree-pruning/难度:☆☆☆题目:给定一个二叉树根节点root,树的每个节点的值要么是0,要么是1。返回移除了所有不包含1的子树的原二叉树。节点node的子树为node本身,以及所有node的后......
  • 二叉树的C++实现
    文章目录一、二叉树存储的物理结构1.1二叉树基础知识1.2二叉树的存储1.2.1单个节点的存储:1.2.2二叉树的存储二、C++代码实现2.1每个二叉树节点结构体:2.2二叉树类的定义2.3方法实现一、二叉树存储的物理结构1.1二叉树基础知识(1)二叉树的定义:每个节点最多......
  • 二叉树遍历
    前序顺序为根左右递归publicstaticvoidpreLoop(TreeNoderoot){System.out.println(root.value);if(root.left!=null){preLoop(root.left);}if(root.right!=null){preLoop(root.right);}}其他使用栈,以根右左的顺......
  • 【Leetcode Top 100】94. 二叉树的中序遍历
    问题背景给定一个二叉树的根节点rootrootroot,返回它的中序遍历。数据约......