CrazyJavaBoy 永久会员 2023年3月24日上午9:52

利用前序遍历和中序遍历的特点找根节点，根据根节点分治

class Solution {
    //map是为了方便根据根节点的值得到其在中序遍历数组中的下标
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) {
            return null;
        }
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return root;
    }
    TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        if(l1 > r1 && l2 > r2) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[l1]);
        //根节点的值得到其在中序遍历数组中的下标
        int i = map.get(preorder[l1]);
        //递归
        root.left = f(preorder, l1 + 1, l1 + (i - l2), inorder, l2 , i -1);
        root.right = f(preorder, l1 + i - l2 + 1, r1, inorder, i + 1, r2);
        return root;
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月13日上午10:42

想清楚build的参数

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0){
            return null;
        }
        //前序遍历：中左右
        //中序遍历：左中右
        //数字和下标建立一个map
        for(int i = 0; i < inorder.length; i ++){
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

    }
    public TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
        //规定构建这棵树的范围
        if(pl > pr || il > ir){
            return null;
        }
        TreeNode node = new TreeNode(preorder[pl]);
        int i = map.get(preorder[pl]);
        node.left = build(preorder, pl + 1, pl + (i - il), inorder, il, i - 1);
        node.right = build(preorder, pl + (i - il) + 1, pr, inorder, i + 1, ir);
        return node;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月4日下午4:46

先找根节点，然后根据根节点分治

时间复杂度 O(N)
空间复杂度 O(N)

class Solution {
    int[] pre, in;
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pre = preorder;
        in = inorder;
        for (int i = 0; i < in.length; i++) map.put(in[i], i);
        return rebuild(0, pre.length-1, 0, in.length-1);
    }

    private TreeNode rebuild(int preL, int preR, int inL, int inR) {
        if (preL > preR) return null;
        TreeNode root = new TreeNode(pre[preL]);
        int idx = map.get(root.val);
        int len = idx - inL;
        root.left = rebuild(preL + 1, preL + len, inL, idx - 1);
        root.right = rebuild(preL + len + 1, preR, idx + 1, inR);
        return root;
    }
}

0 赞同 0 条回复

如梦似歌普通 2023年1月2日下午10:58

class Solution {
        HashMap<Integer,Integer> map = new HashMap<>(); //标记中序遍历
        int[] preorder; //保留的先序遍历
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return recur(0,0,inorder.length-1);
    }

    public TreeNode recur(int root, int left, int right){
        if(left > right)
            return null;
        TreeNode node = new TreeNode(preorder[root]);
        int i = map.get(preorder[root]);
        node.left = recur(root+1, left, i-1);
        node.right = recur(root+i-left+1, i+1, right);
        return node;
    }
}

0 赞同 0 条回复

cute. 普通 2023年1月2日下午10:43

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    // 过滤
    if(!preorder.length || !inorder.length){
        return null
    }

    // 根据先序排序：根左右
    // 所以根就是preorder第一个
    // shift():把数组的第一个元素从其中删除，并返回第一个元素的值
    const rootValue = preorder.shift();
    // 根据中序排序 ：左根右
    //找出根值的下标，进行划分左右区间
    let rootValueIndex = inorder.indexOf(rootValue);
    // 构建树
    const root = new TreeNode(rootValue);
    // 构建左右
    // 根据先序排序：根左右
    // 第一个参数：
    // preorder第二个元素是左区的第一个根节点,所以从第二个元素截取到 根植的下标（0，根植）。slice特性的原因（包左不包右）
    // 然后inorder左边就是0到根植的下标，取左期间
    // slice():从已有的数组中返回选定的元素
    root.left = buildTree(preorder.slice(0,rootValueIndex),inorder.slice(0,rootValueIndex))
    //然后preorder截取根值之后，第二个参数就是拿inorder右区间
    root.right = buildTree(preorder.slice(rootValueIndex),inorder.slice(rootValueIndex+1));
    return root
};

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Gg 普通 2023年1月1日下午11:41

class Solution {
    private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 从先序获取根节点，从中序定位到根节点的位置，分出左右子树
        // 中序分出了左右子树，可以分别计算长度，根据长度将先序中的节点进行截取
        map = new HashMap(inorder.length);
        for(int i = 0; i < inorder.length; i ++){
            map.put(inorder[i],i);
        }
        return findNode(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd,int[] inorder,int inBegin,int inEnd){
        if(preBegin > preEnd || inBegin > inEnd){
            return null;    
        }
        int rootVal = preorder[preBegin];
        TreeNode root = new TreeNode(rootVal);
        // 获取根节点位置
        int rootIndex = map.get(rootVal);
        // 计算左右子树长度
        int leftLength = rootIndex - inBegin;
        int rightLength = inEnd - rootIndex;
        // 递归找左右子树
        root.left = findNode(preorder,preBegin+1,preBegin+leftLength,inorder,inBegin,rootIndex-1);
        root.right = findNode(preorder,preBegin+1+leftLength,preEnd,inorder,rootIndex+1,inEnd);
        return root;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月26日上午11:37

map = {}
def buildTree(self, preorder, inorder) -> TreeNode:
    if not preorder or not inorder:
        return None
    # 存放中序遍历的索引

    for index,_ in enumerate(inorder):
        map[_] = index
    root = makeTree(preorder,0,len(preorder)-1,inorder,0,len(inorder)-1)
    return root



def makeTree(preorder,pre_left_id,pre_right_id,inorder,in_left_id,in_right_id):
    '''
    在前序遍历和中序遍历中不断缩小范围，在缩小范围的过程中构建左右子树
    Args:
        preorder: 前序遍历
        pre_left_id: 该子树在前序遍历中的索引范围的左边界
        pre_right_id: 该子树在前序序遍历中的索引范围的右边界
        inorder: 中序遍历
        in_left_id: 该子树在中序遍历中的索引范围的左边界
        in_right_id: 该子树在中序遍历中的索引范围的右边界

    Returns:

    '''
    if (pre_left_id > pre_right_id) or (in_left_id > in_right_id):
        return None
    root = TreeNode(preorder[pre_left_id])
    root_index = map.get(preorder[pre_left_id])
    root.left = makeTree(preorder, pre_left_id + 1, root_index - in_left_id + pre_left_id, inorder, in_left_id,
                              root_index - 1)
    root.right = makeTree(preorder, root_index - in_left_id + pre_left_id + 1, pre_right_id, inorder,
                               root_index + 1, in_right_id)
    return root

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:18

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder, int preorderbegin,int preorderend, vector<int>& inorder, int inorderbegin, int inorderend){
        if(preorderend==preorderbegin) return nullptr;
        TreeNode* root = new TreeNode(preorder[preorderbegin]);
        if(preorderend-preorderbegin==1) return root;

        int deliemeter;
        for(deliemeter=0;deliemeter<inorder.size();deliemeter++){
            if(inorder[deliemeter]==preorder[preorderbegin]) break;
        }

        //先切割中序
        int leftinorderbegin = inorderbegin;
        int leftinorderend = deliemeter;
        int rightinorderbegin = deliemeter+1;
        int rightinorderend = inorderend;

        int leftpreorderbegin = preorderbegin+1;
        int leftpreorderend = preorderbegin+1+deliemeter-inorderbegin;
        int rightpreorderbegin = leftpreorderend; //左闭右开
        int rightpreorderend = preorderend;

        root->left = traversal(preorder,leftpreorderbegin,leftpreorderend,inorder,leftinorderbegin,leftinorderend);
        root->right = traversal(preorder,rightpreorderbegin,rightpreorderend,inorder,rightinorderbegin,rightinorderend);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = traversal(preorder,0,preorder.size(),inorder,0,inorder.size());
        return root;
    }
};

0 赞同 0 条回复

Tolkien 永久会员 2022年11月17日下午3:48

private HashMap<Integer, Integer> map = new HashMap<>();

    /**
     * 递归+哈希表
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 特殊情况
        int length = preorder.length;
        if (length == 0) {
            return null;
        }

        // 为了方便后续求根节点的索引
         for (int i = 0; i < length; i++) {
            map.put(inorder[i], i);
        }

        return recur(preorder, inorder,0, length-1, 0, length-1);
    }

    TreeNode recur(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {
        // 1. 递归结束条件
        // 若序列为空，则树不存在
        if (l1 > r1 || l2 > r2) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[l1]);
        // 根节点在中序遍历的位置
        int rootIndex = map.get(preorder[l1]);

        // 2. 等价关系式
        root.left = recur(preorder, inorder, l1+1, l1+(rootIndex-l2), l2, rootIndex);
        root.right = recur(preorder, inorder, l1+(rootIndex-l2)+1,r1, rootIndex+1, r2);

        return root;
    }

0 赞同 0 条回复

xye 普通 2022年11月16日下午2:31

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    //通过前序第一个找出root
    root := &TreeNode{preorder[0], nil, nil}
    //利用i找到root在inorder的位置
    i := 0
    for ;inorder[i] != preorder[0]; i++ {
    }
    root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
    root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
    return root
}

时间O(n)空间O(n)

0 赞同 0 条回复

symbol 普通 2022年11月10日下午9:47

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    //先序遍历的第一个值为根节点
    root := &TreeNode{preorder[0], nil, nil}
    //在中序遍历中找到根节点的下标
    i :=0
    for ; i < len(inorder);i++{
        if inorder[i] == preorder[0]{
            break
        }
    }

    left_h := len(inorder[:i]) //左子树的长度 
    root.Left = buildTree(preorder[1:left_h+1],inorder[:i]) //当前节点的左孩子 由前序遍历的左子树和中序遍历的左子树决定
    root.Right = buildTree(preorder[left_h+1:], inorder[i+1:]) //当前节点的右孩子由前序遍历的右孩子和中序遍历的右孩子决定
    return root
}

0 赞同 0 条回复

浅夏的无奈普通 2022年11月9日上午12:27

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
    int[] preorder;//保留的先序遍历，方便递归时依据索引查看先序遍历的值

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //三个索引分别为
        //当前根的的索引
        //递归树的左边界，即数组左边界
        //递归树的右边界，即数组右边界
        return recur(0,0,inorder.length-1);
    }

    TreeNode recur(int pre_root, int in_left, int in_right){
        if(in_left > in_right) return null;// 相等的话就是自己
        TreeNode root = new TreeNode(preorder[pre_root]);//获取root节点
        int idx = map.get(preorder[pre_root]);//获取在中序遍历中根节点所在索引，以方便获取左子树的数量
        //左子树的根的索引为先序中的根节点+1 
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        root.left = recur(pre_root+1, in_left, idx-1);
        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的右边界为中序中原来右子树的边界
        root.right = recur(pre_root + (idx - in_left) + 1, idx+1, in_right);
        return root;

    }
}

0 赞同 0 条回复

黎昕普通 2022年11月8日下午4:47

核心思想：
二叉树先序遍历：【根|左子树|右子树】
二叉树中序遍历：【左子树|根|右子树】
找到根在inorder中的位置，划分inorder为左右子树序列，递归，直到inorder长度为0或者1

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if(preorderSize==1){
        struct TreeNode* tmp=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        tmp->val=*preorder;
        tmp->left=NULL;
        tmp->right=NULL;
        return tmp;
    }
    else if(preorderSize==0){
        return NULL;
    }
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=*preorder;
    int i=0;
    for(;i<inorderSize;i++){
        if(*(inorder+i)==*preorder){
            break;
        }
    }
    root->left=buildTree(preorder+1,i,inorder,i);
    root->right=buildTree(preorder+i+1,preorderSize-i-1,inorder+i+1,inorderSize-i-1);
    return root;
}

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def rebuild(rootindex,leftindex,rightindex):
            # rootindex表示在preorder中的下标，[leftindex,rightindex]表示inorder中的下标
            # 递归基
            if leftindex>rightindex:
                return
            node=TreeNode(preorder[rootindex])
            i=dic[preorder[rootindex]] # 当前root节点在inorder中的值
            node.left=rebuild(rootindex+1,leftindex,i-1)
            node.right=rebuild(rootindex+2,i+1,rightindex)
            node.right=rebuild(rootindex+i-leftindex+1,i+1,rightindex)
            return node


        dic={}
        for i in range(len(inorder)):
            dic[inorder[i]]=i # 建立一个字典，反映射 inorder到i 方便进行查找，避免后续每次进行遍历查找
        return rebuild(0,0,len(inorder)-1)

0 赞同 0 条回复

酥合普通 2022年11月6日下午9:09

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 
    private Map<Integer, Integer> indexMap;


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        indexMap = new HashMap<>(16);
        for(int i = 0; i < inorder.length; i++ ){
            indexMap.put(inorder[i], i);
        }
        return buildTreeRecursive(preorder, inorder, 0, preorder.length - 1, 0, preorder.length);
    }

    public TreeNode buildTreeRecursive(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if(preLeft > preRight) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preLeft]);
        int rootTmp = indexMap.get(preorder[preLeft]);
        root.left = buildTreeRecursive(preorder, inorder, preLeft + 1, preLeft + rootTmp - inLeft, inLeft, rootTmp - 1);
        root.right = buildTreeRecursive(preorder, inorder, preLeft + rootTmp - inLeft + 1, preRight, rootTmp + 1, inRight);
        return root;

    }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

@ 普通 2022年11月5日下午5:13

思路：前序（第一个原素为根节点）和后序（最后一个元素为根节点）用来找根节点，中序遍历用来区分左子树、根节点、右子树.
时间复杂度 O(N)
空间复杂度 O(N)

//前序 + 中序
class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                          // 递归终止
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }
}

//中序 + 后序
class Solution {
    int[] postorder;
    HashMap<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        for (int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(postorder.length - 1, 0, inorder.length - 1);
    }

    TreeNode recur(int root, int left, int right) {
        if (left > right) return null;                          // 递归终止
        TreeNode node = new TreeNode(postorder[root]);          // 建立根节点
        int i = dic.get(postorder[root]);                       // 划分根节点、左子树、右子树
        node.left = recur(root - (right - i) - 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root - 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }


}

0 赞同 0 条回复

lobort 普通 2022年11月5日下午2:26

class Solution {
    //存放前序遍历的映射，快速得到某个元素的下表 hashmap查询时间复杂度O(1)
    Map<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder){
        //特殊情况
        if(preorder == null || preorder.length <= 0){
            return null;
        }
        for(int i = 0; i < preorder.length; i++){
            map.put(inorder[i], i);
        }

        TreeNode root = func(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return root;
    } 

    public TreeNode func(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2){
        //返回条件
        if(l1 > r1 || l2 > r2){
            return null;
        }
        //前序遍历的第一个节点为头节点
        TreeNode root = new TreeNode(preorder[l1]);
        int i = map.get(preorder[l1]);
        //左右子树递归
        root.left = func(preorder, l1 + 1, l1 + (i - l2), inorder, l2, i-1);
        root.right = func(preorder, l1 + (i - l2) + 1, r1, inorder, i + 1, r2);
        //返回结果
        return root;
    }
}

0 赞同 0 条回复

阿白普通 2022年11月5日上午11:30

1、前序遍历的首节点就是根，找到其在中序中的位置i，则中序的前i-1为左子树、前序的1~i也为左子树；右子树同理，对左右采用递归
2、时间O（n），空间O（n）

class Solution {
public:
    map<int, int> pos;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() <= 0)
            return nullptr;
        TreeNode *res;
        for (int i = 0; i < inorder.size(); ++i)
            pos[inorder[i]] = i;

        res = funcC(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        return res;
    }

    TreeNode* funcC(vector<int> &pre, int l1, int r1, vector<int> &ino, int l2, int r2)
    {
        if (l1 >r1 || l2 > r2)
            return nullptr;
        TreeNode* root = new TreeNode(pre[l1]);
        int i = pos[pre[l1]];

        root->left = funcC(pre, l1 + 1, l1 + i - l2, ino, l2, i - 1);
        root->right = funcC(pre, l1 + i - l2 + 1, r1, ino, i + 1, r2);

        return root;
    }
};

0 赞同 0 条回复

just 普通 2022年11月5日上午10:21

//递归建立二叉树
/**
* 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 {
public:
TreeNode fun(vector& pre,vector& in,int l,int r,int start,int end ){
if(l>r) return nullptr;
int target=pre[l];
int pos=-1;
for(int i=start;i<=end;++i){
if(in[i]target){
pos=i;
break;
}
}
TreeNode* newnode=new TreeNode(target);
int len = pos-start;
newnode->left=fun(pre,in,l+1,l+len,start,pos-1);
newnode->right=fun(pre,in,l+len+1,r,pos+1,end);
return newnode;
}
TreeNode* buildTree(vector& preorder, vector& inorder) {
int n=preorder.size();
return fun(preorder,inorder,0,n-1,0,n-1);

};

0 赞同 0 条回复

马啸天永久会员 2022年11月3日上午12:49

class Solution {

    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder , int[] inorder) {
        if (preorder == null || preorder.length <= 0)
            return null;

        //建立中序遍历数组的映射（就是为了快速求出某个元素的下标）
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i] , i);
        }

        TreeNode root = f(preorder , 0 , preorder.length - 1 , inorder , 0 , inorder.length - 1);

        return root;
    }

    TreeNode f(int[] preorder , int l1 , int r1 , int[] inorder , int l2 , int r2) {
        //前序遍历或者中序遍历为空时,表示这棵树不存在，直接返回null
        if (l1 > r1 || l2 > r2) {
            return null;
        }
        //根节点
        TreeNode root = new TreeNode(preorder[l1]);
        //根节点在中序遍历中的下标
        int i = map.get(preorder[l1]);
        // 递归求解
        root.left = f(preorder , l1 + 1 , l1 + (i - l2) , inorder , l2 , i - 1);
        root.right = f(preorder , l1 + (i - l2) + 1 , r1 , inorder , i + 1 , r2);

        return root;
    }
}
我抄的

0 赞同 0 条回复

狗蛋儿普通 2022年11月2日下午10:33

前序和后序这两者同中序之间的关系

也就是中间节点位置

细节：明确位置编号是前闭后开还是前逼后闭

递归就完事了！

class Solution {
public:
    TreeNode* traveral(vector<int> pre,vector<int> vin,int preBegin,int preEnd,
                                                       int vinBegin,int vinEnd){
        if(preBegin == preEnd) return nullptr;
        TreeNode *root  = new TreeNode(pre[preBegin]);
        int rootVal = pre[preBegin];
        if(preEnd - preBegin == 1) return root;
        int rootValPoint ;
        for(int i = vinBegin ;i< vinEnd;i++){
            if(vin[i] == rootVal){
                rootValPoint = i;
                break;
            }
        }
        //切割中序数组
        //左中序
        int vinLeftBegin = vinBegin;
        int vinLeftEnd   = rootValPoint;
        //右中序
        int vinRightBegin = rootValPoint +1;
        int vinRightEnd   = vinEnd;


<pre><code>    //切割前序
    //左前序
    int preLeftBegin = preBegin +1;
    int preLeftEnd   = preLeftBegin + rootValPoint-vinBegin;
    //右前序
    int preRightBegin = preLeftBegin + rootValPoint-vinBegin;
    int preRightEnd   = preEnd;

    root->left = traveral(pre,  vin, preLeftBegin, preLeftEnd, vinLeftBegin, vinLeftEnd);
    root->right = traveral(pre, vin, preRightBegin, preRightEnd, vinRightBegin, vinRightEnd);


    return root;                                                   
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    if(pre.size() == 0  || vin.size() == 0) return nullptr;
    return traveral(pre,vin,0,pre.size(),0,vin.size());
}
</code></pre>

};

0 赞同 0 条回复

优秀市民普通 2022年11月2日下午9:47

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

时间复杂度on

0 赞同 0 条回复

你有点可爱喔普通 2022年11月2日下午7:36

时间 O(n) 空间 O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if(preorder == null || preorder.length<=0){
            return null;
        }
        for(int i = 0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        TreeNode root = fun(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        return root;

    }
    TreeNode fun(int [] preorder,int l1,int r1,int [] inorder,int l2,int r2){
        if(l1>r1 && l2>r2){
            return null;
        }
        TreeNode root = new TreeNode(preorder[l1]);
        int i = map.get(preorder[l1]);
        root.left = fun(preorder,l1+1,l1+(i-l2),inorder,l2,i-1);
        root.right = fun(preorder,l1+(i-l2)+1,r1,inorder,i+1,r2);
        return root;

    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年11月2日上午12:32

解题思路：根节点在前序遍历中的子树节点中的第一个，通过构建哈希表快速找到其在中序遍历中的位置，左右子树分别位于中序遍历根节点的两端，再找到左右子树开始和结束的索引，递归调用子树构造得到最终结果。
时间复杂度：O（n）
空间复杂度：O（n）

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def bulidSubTree(preorder_left, preorder_right, inorder_left, inorder_right):
            if preorder_left > preorder_right:
                return None

            # 前序遍历中的根节点
            preorder_root = preorder_left
            # 构造根节点
            root = TreeNode(preorder[preorder_root])
            # 该根节点在中序遍历中的位置
            inorder_root_index = index[preorder[preorder_root]]
            # 该格根节点下的左子树的节点数目
            left_node_size = inorder_root_index - inorder_left
            # 递归构造左子树，并连接到根节点
            root.left = bulidSubTree(preorder_left+1, preorder_left+left_node_size,inorder_left,inorder_root_index-1)
            # 递归构造右子树，并连接到根节点
            root.right = bulidSubTree(preorder_left+left_node_size+1, preorder_right, inorder_root_index+1, inorder_right)
            return root

        n = len(preorder)
        index = {elem:i for i,elem in enumerate(inorder)}
        return bulidSubTree(0,n-1,0,n-1)

0 赞同 0 条回复

Whatever 永久会员 2022年11月1日下午6:48

时间O(n)，空间O(n)

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder,int preStart,int preEnd,int[]inorder,int inStart,int inEnd){
        if(preStart > preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        int index = 0;
        for(int i = 0;i < inorder.length;i++){
            if(inorder[i] == rootVal){
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        int leftsize = index - inStart;
        root.left = build(preorder,preStart+1,preStart+leftsize,inorder,inStart,index-1);
        root.right = build(preorder,preStart+leftsize+1,preEnd,inorder,index+1,inEnd);
        return root;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月1日下午5:19

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        Map<Integer,Integer> indexMap = new HashMap<>();
        for(int i=0;i<n;i++){
           indexMap.put(inorder[i],i);
        }
        return MybuildTree(preorder,inorder,0,n-1,0,n-1);
    }

    public TreeNode MybuildTree(int[] preorder,int[] inorder,int preorder_left, int preorder_right,int inorder_left,int inorder_right){
        Map<Integer,Integer> indexMap = new HashMap<>();

        if(preorder_left>preorder_right) return null;
        int preorder_root = preorder_left;
        int inorder_root = indexMap.get(preorder[preorder_root]);
        int left_size = inorder_root-inorder_left;
        TreeNode root = new TreeNode(preorder[preorder_root]);
        root.left = MybuildTree(preorder,inorder,preorder_left+1,preorder_left+left_size,inorder_left,inorder_root-1);
        root.right =MybuildTree(preorder,inorder,preorder_left+left_size+1,preorder_right,inorder_root+1,inorder_left);
        return root;
    }                         
}

空间时间复杂度O(n）

0 赞同 0 条回复

派大星普通 2022年11月1日下午4:56

class Solution {
//二叉树自上而下，使用递归的方法建立子节点，链接到父亲节点的left和right
//时间复杂度O(2^n)
//空间复杂度O(n)
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||preorder.length==0){
            return null;
        }
        if(preorder.length==1){
            return new TreeNode(preorder[0]);
        }
        int b = 0;
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==preorder[0]){
                b = i;
                break;
            }
        }
        TreeNode node = new TreeNode(preorder[0]);
        if(b!=0)
        node.left = buildTree(Arrays.copyOfRange(preorder,1,b+1),Arrays.copyOfRange(inorder,0,b));
        if(b+1< preorder.length)
        node.right = buildTree(Arrays.copyOfRange(preorder,b+1,preorder.length),
                Arrays.copyOfRange(inorder,b+1,inorder.length));

        return node;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月1日下午4:21

时间复杂度为O（n）,空间复杂度为O（n）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //哈希map函数用来记录中序遍历的节点和节点对应的下标，找到前序遍历的根节点时就能找到中序遍历与之对应的节点下标
         map = new HashMap<>();
         for(int i=0;i < inorder.length;i++){
             map.put(inorder[i],i);
         }
         TreeNode root = f(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
         return root;
    }
    TreeNode f(int[] preorder,int l1,int r1,int[] inorder,int l2,int r2){
        if(l1>r1||l2>r2){
            return null;
        }
        TreeNode root = new TreeNode(preorder[l1]);
        int i = map.get(root.val);
        root.left = f(preorder,l1+1,l1+(i-l2),inorder,l2,i-1);
        root.right = f(preorder,l1+(i-l2)+1,r1,inorder,i+1,r2);
        return root;
    }
}

0 赞同 0 条回复

T 普通 2022年11月1日下午4:21

class Solution {
    int[] p;
    //用来存储中序数组的值和下标。
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.p = preorder;
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return rec(0, 0, inorder.length - 1);
    }

    public TreeNode rec(int root, int l, int r) {
        if(l > r) return null;
        //前序遍历的最前面就是根
        TreeNode node = new TreeNode(p[root]);
        //获取到中序数组中该值的下标，左边就是左子树，右边就是右子树。
        int i  = map.get(p[root]);
        node.left = rec(root + 1, l, i - 1);
        //在前序数组中求右子树的根节点下标，需要减去左子树的长度。  
        node.right = rec(root + i - l + 1, i + 1, r);
        return node;
    }
}

0 赞同 0 条回复

小肸永久会员 2022年11月1日下午2:32

思路：根据前序遍历和中序遍历的特点构建二叉树，用代码实现就行。
实现方式有递归，可以在递归中确定根节点位置的下标，这样时间复杂度应该为O(N^2)，空间复杂度为O(height(树的高度))。如果先用map存储中序遍历中值与下标位置之间的关系，那递归中确定根节点位置的下标的时间复杂度就为O(1)，递归N次，总的时间复杂度为O(N)，空间复杂度为O(N（一个哈希表的空间）)。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeCore(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    private TreeNode buildTreeCore(int[] preorder, int[] inorder, int startPre, int endPre, int startIn, int endIn)
    {
        if (endPre < startPre || endIn < startIn) {
            return null;
        }
        // 获取根节点的值
        int rootValue = preorder[startPre];
        // 创建根节点
        TreeNode root = new TreeNode(rootValue);
        // 找到根节点的值出现在中序遍历中的下标位置
        int rootIndex = startIn;
        while (inorder[rootIndex] != rootValue) {
            if (rootIndex > endIn) {
                throw new IllegalArgumentException("error");
            }
            rootIndex ++;
        }
        // 递归构建左子树，连接左子树的根节点
        root.left = buildTreeCore(preorder, inorder, startPre + 1, startPre + (rootIndex - startIn), startIn, rootIndex - 1);
        // 递归构建右子树，连接右子树的根节点
        root.right = buildTreeCore(preorder, inorder, startPre + (rootIndex - startIn) + 1, endPre, rootIndex + 1, endIn);
        return root;
    }
}

实现方式还可以是迭代：想想如果这颗二叉树是一个只有左子树的单链表，那么前序和中序它们是不是逆序的，要考虑右子节点什么时候出现。时间复杂度O（N)，空间复杂度取决于栈中同时存放的最多节点个数，为O(height）。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Stack stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        int index = 0;
        for (int i = 1; i < preorder.length; i ++) {
            TreeNode node = stack.peek();
            if (node.val != inorder[index]) {
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && inorder[index] == stack.peek().val) {
                    node = stack.pop();
                    index ++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

0 赞同 0 条回复

庄重普通 2022年11月1日下午2:32

//  思路：
//     1.前序遍历的第一个节点为根节点，通过该节点可以找到中序遍历中的左子树和右子树
//     2.通过中序遍历得到左右子树的下标范围，即可得到前序遍历中的左右子树
//     3.此时，分别找到了左子树的前序遍历和中序遍历  以及右子树的前序遍历和中序遍历
//     4.由此，便可把问题分解为两个子问题，通过递归便可得到答案
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || preorder.size()<=0)
            return NULL;

        for(int i = 0;i<inorder.size();++i){
            mymap.insert(pair<int,int>(inorder[i],i));
        }
        TreeNode* root = f(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);

        return root;

    }
    //递归的时候不需要改变数组中的值，加上const比较好
    //函数功能：构建二叉树
    TreeNode* f(const vector<int>& preorder, int l1, int r1,const vector<int>& inorder ,int l2, int r2){
        //结束条件(初始值)： 没有左右子树，进行递归结束
        if(l1>r1 && l2>r2)
            return NULL;

        TreeNode* pRoot = new TreeNode(preorder[l1]);
        int i = mymap[preorder[l1]];
        //关系式
        pRoot->left = f(preorder,l1+1, l1+(i-l2),inorder, l2,i-1);
        pRoot->right = f(preorder,l1+(i-l2)+1, r1,inorder, i+1,r2);

        return pRoot;

    }
    //每次递归都需要得到得到中序遍历数组中的代表根节点的位置，
    //用map进行保存很有必要，减少每次需要的循环
    map<int,int> mymap;

};
//时间复杂度O(n) 
//空间复杂度O(n)

0 赞同 0 条回复

y 普通 2022年11月1日下午2:09

var buildTree = function(preorder, inorder) {
   if(preorder.length === 0) {
      return null;
   }
    // 前序遍历的第一个节点就是当前根节点
    let rootVal = preorder.shift();
    // 找到当前根节点在中序遍历 数组的位置
    let index = inorder.indexOf(rootVal);
    // 创建根节点
    let root = new TreeNode(rootVal);
    root.left = buildTree(preorder.slice(0, index),inorder.slice(0, index));
    root.right = buildTree(preorder.slice(index), inorder.slice(index + 1));
    return root;
};

0 赞同 0 条回复

是梦终空永久会员 2022年11月1日上午11:53

递归,本来是想遍历查找的i的位置，看了视频才想到可以用map
时间O(n)
空间O(n)

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null && preorder.length == 0)    return null;
        for(int i = 0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    TreeNode dfs(int[] preorder,int lp,int rp,int[] inorder,int li,int ri){
        if(lp>rp && li>ri){
            return null;
        }
        TreeNode root = new TreeNode(preorder[lp]);
        int i = map.get(preorder[lp]);

        root.left = dfs(preorder,lp+1,lp+(i-li),inorder,li,i-1);
        root.right = dfs(preorder,lp+(i-li)+1,rp,inorder,i+1,ri);
        return root;
    }
}

0 赞同 0 条回复

追普通 2022年11月1日上午10:35

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++){
            dic[inorder[i]] = i;

        }
        return recur(0, 0, inorder.size()-1);
    }

private:
    vector<int> preorder;
    unordered_map<int, int> dic;
    TreeNode* recur(int root, int left, int right){
        if(left > right) return nullptr;
        TreeNode* node = new TreeNode(preorder[root]);
        int i = dic[preorder[root]];
        node->left = recur(root + 1, left, i-1);
        node->right = recur(root + i - left + 1, i + 1, right);
        return node;
    }
};

寻找左子树和右子树节点部分还是觉得有点迷糊，需要再仔细看一下

0 赞同 0 条回复

天然普通 2022年10月31日下午11:24

迭代思想，用前序作为C位，中序作为辅助位，我们去遍历前序结点的同时，去判别和移动中序列表，如果当前结点的值和中序不同，则还没有到最左，把前序的值付给结点的左边，如果相同，返还前一结点，看是否和中序列表相同，不同了，则左到尽头，把前序列表的值付给结点的右边，还是不好想，我想的是用前序的根和中序的根，把中序作为C位判别，但不得行。时间复杂度O(n) 空间复杂度O(n)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not (preorder and inorder): return None
        root  = TreeNode(preorder[0])
        num = [root]
        index = 0
        for i in range(1, len(preorder)):
            value = preorder[i]
            cur = num[-1]
            if cur.val != inorder[index]:
                cur.left = TreeNode(value)
                num.append(cur.left)
            else:
                while num and num[-1].val == inorder[index]:
                    cur = num.pop()
                    index += 1
                cur.right = TreeNode(value)
                num.append(cur.right)
        return root

0 赞同 0 条回复

青木普通 2022年10月31日下午11:20

/**
    感觉能想到先找到根节点再将左右子树分开，但就是写不出来，g
    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode function(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) {
        if(pre_left > pre_right) return null;

        int pre_root = preorder[pre_left];
        int in_root = indexMap.get(preorder[pre_left]);

        int left_size = in_root - in_left;
        TreeNode root = new TreeNode(pre_root);

        root.left = function(preorder, inorder, pre_left+1, pre_left+left_size, in_left, in_root-1);
        root.right = function(preorder, inorder, pre_left+left_size+1, pre_right, in_root+1, in_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++){
            indexMap.put(inorder[i], i);
        }
        return function(preorder, inorder, 0, n-1, 0, n-1);
    }
}


/**
    迭代法感觉有点难想...
    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null || preorder.length==0) return null;

        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        int index = 0;
        for(int i=1; i<preorder.length; i++){
            TreeNode node = stack.peek();
            if(node.val != inorder[index]){
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            }
            else{
                while(!stack.isEmpty() && stack.peek().val == inorder[index]){
                    node = stack.pop();
                    index++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月31日下午10:14

1、根据前序遍历和中序遍历来重建二叉树，要注意前序遍历和中序遍历的性质及其之前的关系
2、前序遍历的第一个元素为根节点，找到这个节点在中序遍历中的位置，在中序遍历中往前是左子树节点，往后是右子树节点，根据左子树节点数量，也能在前序遍历中判断出哪些是左子树节点，哪些是右子树节点
3、那如何找到根节点在中序遍历中的位置呢？利用map容器，重建二叉树之前先将中序遍历的节点值和其位置索引存入map中
时间复杂度O(n) 空间复杂度O(n)

class Solution {
private:
    unordered_map<int,int> map;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || preorder.size() <= 0) return NULL;
        for(int i = 0;i < inorder.size();i++){
            map.insert(pair<int,int>(inorder[i],i));
        }
        TreeNode* root = f(preorder,0,preorder.size()-1,inorder,0,preorder.size()-1);
        return root;
    }
private:
    TreeNode* f(vector<int>& preorder,int l1,int r1,vector<int>& inorder,int l2,int r2){
        if(l1 > r1 || l2 > r2) return NULL;
        TreeNode* node = new TreeNode(preorder[l1]);
        int i = map[preorder[l1]];
        node->left = f(preorder,l1+1,l1+(i-l2),inorder,l2,i-1);
        node->right = f(preorder,l1+(i-l2)+1,r1,inorder,i+1,r2);
        return node;
    } 
};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月31日下午10:05

剑指 Offer 07. 重建二叉树(10.31)

递归

/**
时间复杂度O(N) :在创建Map时遍历使用O(N)
空间复杂度O(N) :mapO(N),递归时当退化成链表时，系统栈的复杂度为O(N)
 */
class Solution {
    HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length <= 0) return null;//二叉树不存在
        for(int i = 0;i < inorder.length;i++){
            map.put(inorder[i],i);//将中序遍历中的元素和下标构建映射，方便查询
        }
        return build(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
    }
    //l1,r1表示preorder中需要创建的区间，同理l2,r2
    public TreeNode build(int[] preorder,int l1,int r1,int[] inorder,int l2,int r2){
        // 前序遍历或者中序遍历为空时，直接返回 null
        if(r1 < l1 || r2 < l2) return null;
        TreeNode root = new TreeNode(preorder[l1]);
        int i = map.get(preorder[l1]);//找到中序遍历中的根节点，分割左右子树
        root.left = build(preorder,l1+1,l1+(i - l2),inorder,l2,i - 1);
        root.right = build(preorder,l1+(i - l2) + 1,r1,inorder,i + 1,r2);
        return root;
    }

}

106. 从中序与后序遍历序列构造二叉树(10.31)

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
/***
后序的末尾为根节点
 */
class Solution {
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i = 0;i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return findTree(inorder,0,inorder.length,postorder,0,postorder.length);

    }
    public TreeNode findTree(int[] inorder,int inStart,int inEnd,int[]postorder,int postStart,int postEnd){
        //采用左闭右开
       if(inStart >= inEnd || postStart >= postEnd){
           return null;
       }
       TreeNode root = new TreeNode(postorder[postEnd - 1]);
       int rootIndex = map.get(postorder[postEnd - 1]);//获取中序遍历中的根节点位置
       int leftLen = rootIndex - inStart;
       root.left = findTree(inorder,inStart,rootIndex,postorder,postStart,postStart + leftLen);
       root.right = findTree(inorder,rootIndex + 1,inEnd,postorder,postStart + leftLen, postEnd - 1); 
       return root;
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年10月31日下午9:35

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    private TreeNode build(int[] pre, int pS, int pE, int[] in, int iS, int iE) {
        if(iS > iE) {
            return null;
        }
        int val = pre[pS];
        TreeNode node = new TreeNode(val);
        int idx = map.get(val);
        int len = idx - iS;// 保存中序左子树个数，用来确定前序数列的个数
        node.left = build(pre, pS+1, pS+len, in, iS, idx-1);
        node.right = build(pre, pS+len+1, pE, in, idx+1, iE);
        return node;
    }
}

0 赞同 0 条回复

So 普通 2022年10月31日下午8:15

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return root;
    }

    TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        if (l1 > r1 && l2 > r2) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[l1]);
        int i = map.get(preorder[l1]);
        root.left = f(preorder, l1 + 1, l1 + i - l2, inorder, l2, i - 1);
        root.right = f(preorder, l1 + i - l2 + 1, r1, inorder, i + 1, r2);
        return root;
    }
}

时间：O(n)，空间：O(n)

0 赞同 0 条回复

【二叉树专题】剑指 Offer 07. 重建二叉树

共以下 39 个回答

先找根节点，然后根据根节点分治

前序和后序这两者同中序之间的关系

也就是中间节点位置

细节：明确位置编号是前闭后开还是前逼后闭

递归就完事了！

剑指 Offer 07. 重建二叉树(10.31)

106. 从中序与后序遍历序列构造二叉树(10.31)

# 回答此问题取消回复

【二叉树专题】剑指 Offer 07. 重建二叉树

共以下 39 个回答

先找根节点，然后根据根节点分治

前序和后序这两者同中序之间的关系

也就是中间节点位置

细节：明确位置编号是前闭后开还是前逼后闭

递归就完事了！

剑指 Offer 07. 重建二叉树(10.31)

106. 从中序与后序遍历序列构造二叉树(10.31)

# 回答此问题 取消回复

# 回答此问题取消回复