山川湖海普通 2023年8月3日下午9:47

/**
 * 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* build(vector<int>& preorder,int preBegin, int preEnd, vector<int>& inorder, int inBegin, int inEnd) {
        if (preBegin >= preEnd) return nullptr;
        int rootVal = preorder[preBegin];
        TreeNode* root = new TreeNode(rootVal);
        int index = 0;
        for (index = inBegin; index < inEnd; index ++) {
            if (rootVal == inorder[index]) break;
        }
        // 划分中序数组
        int inLeftBegin = inBegin;
        int inLeftEnd = index;
        int inRightBegin = index+1;
        int inRightEnd = inEnd;
        // 划分前序数组
        int len = index - inBegin;
        int preLeftBegin = preBegin+1;
        int preLeftEnd = preLeftBegin + len; // )
        int preRightBegin = preLeftBegin + len; // [
        int preRightEnd= preEnd;

        root->left = build(preorder, preLeftBegin, preLeftEnd, inorder, inLeftBegin, inLeftEnd);
        root->right = build(preorder, preRightBegin, preRightEnd, inorder, inRightBegin, inRightEnd);
        return root;
    }

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

0 赞同 0 条回复

ppopp 普通 2023年8月2日上午12:38

/**
* 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 {
private:
unordered_map<int, int> index; // 结点和中序遍历位置的对应关系

public:
TreeNode* tempbuildTree(vector& preorder, vector& inorder, int prel, int prer, int inl, int inr){
if(prel > prer) return nullptr;

    //前序遍历的第一个结点为根
    int preroot = prel;
    //定位到中序遍历中根节点的位置
    int inroot = index[preorder[preroot]];

    //建立一个根节点
    TreeNode* root = new TreeNode(preorder[preroot]);
    //中序遍历：定位左子树和右子树的位置和左子树和右子树的长度
    int leftsize = inroot - inl;
    //递归建立左子树[inl, inroot-1] 
    root->left = tempbuildTree(preorder, inorder, prel+1, prel+leftsize, inl, inroot-1); 
   //右子树[inroot+1,inr]
    root->right = tempbuildTree(preorder, inorder, prel+leftsize+1, prer, inroot+1, inr);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    for (int i = 0; i < n; ++i) {
        index[inorder[i]] = i; //hash, 索引，中序数值对应前序位数
    }
    return tempbuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}

};

0 赞同 0 条回复

doordie. 普通 2023年7月27日上午10:05

递归区间/分治算法

public class 重构二叉树 {
    /**
     * 标记中序遍历
     */
   HashMap<Integer, Integer> map = new HashMap<>();
    /**
     * 保留的先序遍历
     */
    int[] preorder;


    /**
     * 重构二叉树
     * @return 三个索引分别是
     * 当前根节点的索引、
     * 数组的左边界、
     * 数组的右边界
     */
    public TreeNode buildTree(int[] preorder,int[] inorder){
        this.preorder = preorder;
        // 把中序遍历的值和索引存储到Hash表
        for(int i = 0; i < preorder.length; i++){
            map.put(inorder[i], i);
        }
        // 前序遍历当前根节点的索引
        // 数组的左边界
        // 数组的右边界
        return recur(0,0,inorder.length-1);

    }

    public TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) {
            // 如果左边界>右边界，终止
            return null;
        }
        //获取root节点
        TreeNode root = new TreeNode(preorder[pre_root]);
        //获取中序遍历中根节点的索引
        int idx = map.get(preorder[pre_root]);
        //左子树的根节点 索引是根节点+1
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为原来中序中根节点索引-1
        root.left = recur(pre_root+1,in_left,idx-1);
        //右子树的根节点 索引是 idx-in_left+root+1   根节点索引+左子树长度+1
        //递归右子树的左边界为idx+1
        //递归右子树的右边界为in_right
        root.left = recur(pre_root + (idx - in_left) + 1,idx+1,idx-1);
        return root;
    }


}

时间复杂度：有N个节点，初始化HashMap遍历一次inorder，用时O（n）。递归共建立N个节点，每层递归节点建立占用O（1），总共需要O（n）
空间复杂度：HashMap额外使用O（n）的空间因此是O（n）

0 赞同 0 条回复

小季同学普通 2023年7月27日上午9:19

ts

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    // 边界判断 
    if(!preorder.length || !inorder.length) {
        return null
    }
    // 取到根节点
    const rootValue = preorder[0]
    // 去到中序遍历的中间节点
    const index = inorder.indexOf(rootValue)
    // 将中序遍历分为两半
    // 构建树
    const root = new TreeNode(rootValue)

    // 递归
    root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index))
    root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1))
    return root
};

0 赞同 0 条回复

CKX 普通 2023年7月22日下午3:44

func buildTree(preorder []int, inorder []int) *TreeNode {
    m := make(map[int]int)
    for i, v := range inorder {
        m[v] = i
    }

    var traverse func(int, int, int, int) *TreeNode
    traverse = func(l1, r1, l2, r2 int) *TreeNode {
        if l1 > r1 || l2 > r2 {
            return nil
        }
        root := &TreeNode{preorder[l1],nil,nil}
        i := m[preorder[l1]]
        root.Left = traverse(l1+1, l1+i-l2, l2, i-1)
        root.Right = traverse(l1+i-l2+1, r1, i+1, r2)
        return root
    }
    return traverse(0, len(preorder)-1, 0, len(inorder)-1)
}

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

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月22日下午3:16

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

    // 需要知道区间的首尾
    // 前序的首就是根节点
    public TreeNode recur(int[] preorder,int[] inorder,int prefirst,int prelast, int infirst,int inlast){
        // 递归终止位置
        if(infirst>inlast||prefirst>prelast){
            return null;
        }
        TreeNode root = new TreeNode(preorder[prefirst]);
        int inIndex = map.get(preorder[prefirst]);
        int leftLength = inIndex-infirst;
        int rightLegth = inlast-inIndex;
        // 不要弄错区间的位置
        root.left = recur(preorder,inorder,prefirst+1,prefirst+leftLength,infirst,inIndex-1);
        root.right = recur(preorder,inorder,prelast-rightLegth+1,prelast,inlast-rightLegth+1,inlast);
        return root;
    }
}

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

北辰普通 2023年7月21日下午7:12

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

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        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);
    }

    private 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;
        //递归构造左子树，并连接到根节点
        root.left = myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);
        //递归构造右子树
        root.right = myBuildTree(preorder,inorder,preorder_root+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);
        return root;
    }
}

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

0 赞同 0 条回复

片言莫语普通 2023年7月20日下午5:13

“`java
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 条回复

普通 2023年7月19日下午5:19

c++代码递归回调
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder)
{
return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
TreeNode* build(vector& preorder,int preStart,int preEnd,vector& inorder,int instart,int inEnd)
{
if(preStart>preEnd||instart>inEnd) return NULL;
int val=preorder[preStart];
int index;
TreeNode* temp=new TreeNode(val);
for(int i=0;i<inorder.size();i++)
{
if(valinorder[i])
{
index=i;
break;
}
}
int tleft=index-instart;
temp->left=build(preorder,preStart+1,preStart+tleft+1,inorder,instart,index-1);
temp->right=build(preorder,preStart+tleft+1,preEnd,inorder,index+1,inEnd);
return temp;
}
};

0 赞同 0 条回复

Mby 普通 2023年7月18日下午5:54

/**
 * 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){
        //前序和中序遍历为空时说明这棵树不存在，返回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 条回复

枫梓。普通 2023年7月18日下午4:32

class Solution {
private:
    unordered_map<int, int> idx;
    TreeNode* myTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        int proot = preorder_left;
        int iroot = idx[preorder[proot]];
        TreeNode * root = new TreeNode(preorder[preorder_left]);
        int size = iroot - inorder_left;
        root->left = myTree(preorder, inorder, preorder_left + 1, preorder_left + size, inorder_left, iroot - 1);
        root->right = myTree(preorder, inorder, preorder_left + size + 1, preorder_right, iroot + 1, inorder_right);
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i++) {
            idx[inorder[i]] = i;
        }
        return myTree(preorder, inorder, 0, n-1, 0, n -1);
    }
};

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月18日下午2:42

class Solution {
    Map<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 diguiTree(0, 0, inorder.length-1);


    }

    public TreeNode diguiTree(int root, int left, int right) {
        if (left > right)
            return null;

        TreeNode preTreeNode = new TreeNode(preorder[root]);
        // 递归构建左子树
        Integer inindex = map.get(preorder[root]);//获取在中序遍历中根节点所在索引，以方便获取左子树的数量
        //左子树的根的索引为先序中的根节点+1
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        preTreeNode.left = diguiTree(root+1, left, inindex-1);
        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的右边界为中序中原来右子树的边界
        preTreeNode.right = diguiTree(root+(inindex-left)+1, inindex+1, right);

        return preTreeNode;
    }



}

0 赞同 0 条回复

人生何处不青山普通 2023年7月18日上午11:33

TS写的

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (preorder.length === 0) {
        return null;
    } else if (preorder.length === 1) {
        return new TreeNode(preorder[0]);
    }
    let node = new TreeNode(preorder[0]);
    let index = inorder.findIndex((val) => val === preorder[0]);
    node.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
    node.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
    return node;
};

0 赞同 0 条回复

June 普通 2023年7月18日上午9:26

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len (preorder) == 0 {
        return nil
    }

    node := &TreeNode {
        Val : preorder[0],
        Left : nil,
        Right : nil,
    }
    midVal := preorder[0]
    midIndex := 0
    for i:=0 ; i < len(inorder) ; i++ {
        if inorder[i] == midVal {
            midIndex = i
            break
        }
    }
//递归左右子树
    node.Left = buildTree(preorder[1:midIndex+1], inorder[0:midIndex])
    node.Right = buildTree(preorder[midIndex+1:len(preorder)], inorder[midIndex+1:len(inorder)])
    return node
}

0 赞同 0 条回复

AD钙奶普通 2023年7月17日下午9:52

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

    public TreeNode traversal(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart,int inEnd) {
        if(preStart > preEnd || inStart > inEnd) return null;
        int val = preorder[preStart];
        TreeNode root = new TreeNode(val);
        int index = map.get(val);

        int leftSize = index - inStart; //左子树长度

        root.left = traversal(preorder,inorder,preStart + 1,preStart + leftSize, inStart,index - 1);
        root.right = traversal(preorder,inorder,preStart + leftSize + 1,preEnd, index + 1,inEnd);

        return root;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月17日下午7:59

大致懂了,

/**
 * 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:
    unordered_map<int, int> map;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            map[inorder[i]] = i;
        }
        return helper(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }

    TreeNode* helper(vector<int>& preorder, vector<int>& inorder,int preStart,int preEnd,int inStart,int inEnd) {
        //base case是怎么想出来的?
        if(preStart > preEnd){
            return nullptr;
        }
        int rootVal = preorder[preStart];
        int index = map[rootVal];

        TreeNode *root = new TreeNode(rootVal);

        root->left = helper(preorder,inorder,preStart+1,index-inStart+preStart,inStart,index-1);
        root->right = helper(preorder,inorder,index-inStart+preStart+1,preEnd,index+1,inEnd);


        return root;
    }
};

0 赞同 0 条回复

#00456B 普通 2023年7月17日下午5:47

思路

首先需要了解前序遍历和中序遍历。可知的是前序遍历的第一个为根节点，可以以此作为index来查找在中序遍历中的位置，从而划分出左子树和右子树。
” alt=”在这里插入图片描述” />
以此树为例：
前序遍历为[3, 9, 20, 15, 7]
中序遍历为[9, 3, 15, 20, 7]
其中根节点为[3, 9, 20, 15, 7]中的3，在中序遍历中的位置为[9, 3, 15, 20, 7]。
所以可以划分左右子树为
前序遍历为[3, (9), {20, 15, 7}]
中序遍历为[(9), 3, {15, 20, 7}]

然后可以继续分解为子问题，针对每一个树再重复一次，所以这里需要一个函数。

这个函数需要定义要分解的子树再前序遍历中的左边界l1和右边界r1，以及在中序遍历中的左边界l2和右边界r2。

TreeNode* build(vector<int>& preorder, int l1, int r1, vector<int>& inorder, int l2, int r2)

这是一个递归函数，所以要确定结束条件为左边界超过右边界

        if(l1 > r1 && l2 > r2){
            return NULL;
        }

然后需要探讨子树的边界怎么划分。

首先要得到根节点在中序遍历中的下标i
对于根节点的左子树，其中序遍历数组为
[(9), 3, {15, 20, 7}]
根节点的下标为i
左子树的左边界为l2，右边界为i - 1
右子树的左边界为i + 1，右边界为r2

前序遍历数组为
[3, (9), {20, 15, 7}]
根节点的下标为l1
左子树的左边界l1 + 1，右边界为l1 + (i - l2)
右子树的左边界为l1 + (i - l2) + 1，其实就是左子树右边界+1，右边界为r2
然后在主函数中先对中序遍历进行映射，然后运行递归函数，得到结果。

代码

class Solution {
public:
    //用哈希表来映射中序遍历的值和下标
    unordered_map<int,int> umap;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++){
            umap[inorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode* build(vector<int>& preorder, int l1, int r1, vector<int>& inorder, int l2, int r2){
        //终止条件
        if(l1 > r1 && l2 > r2){
            return NULL;
        }
        //先定义root节点
        TreeNode* root = new TreeNode(preorder[l1]);
        //找到中序遍历中的root节点，即前序遍历的第一个
        int i = umap[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;
    }
};

1 赞同 0 条回复

Mooby 普通 2023年7月17日下午5:36

九
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int[] preorder;
Map<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;
}
}

0 赞同 0 条回复

艺普通 2023年7月17日下午5:11

“`c++
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
if(preorder.empty()||inorder.empty()) return NULL;
int size=preorder.size();
TreeNode* T= new TreeNode(preorder[0]);
auto k=find(inorder.begin(),inorder.end(),*preorder.begin());
vector iLeft(inorder.begin(),k),iRight(k+1,inorder.end());
int n=iLeft.size();
vector pLeft(preorder.begin()+1,preorder.begin()+1+n),pRight(preorder.begin()+1+n,preorder.end());
T->left=buildTree(pLeft,iLeft);
T->right=buildTree(pRight,iRight);
return T;
}
};
“`

0 赞同 0 条回复

NullPointerException 普通 2023年7月17日下午4:48

class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//通过前序遍历划分中序遍历的左右子树
//递归完成每个子树的构建
if(preorder.length0||preordernull)
{
return null;
}
return buildTree1(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode buildTree1(int []preorder,int preorderleft,int preorderright,int [] inorder,int inorderleft,int inorderright)
{
if(preorderleft>preorderright||inorderleft>inorderright)
{
return null;
}
if(inorderleftinorderright)
{
return new TreeNode(inorder[inorderleft]);
}
int find = 0;
for(int i=inorderleft;i<=inorderright;i++)
{
if(preorder[preorderleft]inorder[i])
{
find = i;
}
}
TreeNode root =new TreeNode(preorder[preorderleft]);
root.left=buildTree1(preorder,preorderleft+1,preorderright,inorder,inorderleft,find-1);
root.right=buildTree1(preorder,preorderleft+1+(find-inorderleft),preorderright,inorder,find+1,inorderright); //有坑对于右子树在前序里的第一个要排除前序里的左子树数量
return root;

}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月17日下午3:23

”’java
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return localTree(preorder,inorder,0,preorder.length,0,inorder.length);
}
//算上起始点，包含起始点
public TreeNode localTree(int[] preorder,int[] inorder,int beginPre,int endPre,int beginOr,int endOr){
if(preorder.length 0 || inorder.length 0){
return null;
}
//前序遍历的该结点一定为root
int val = preorder[beginPre];
TreeNode root = new TreeNode(val);
//找到begin在inorder的位置，将其分为左子树和右子树
int count = beginOr;
for(int i = beginOr;i < endOr;i++){
if(inorder[i] val){
count = i;
break;
}
}
int len = count – beginOr;
int left = beginPre + len;
if(left > beginPre){
root.left = localTree(preorder,inorder,beginPre+1,left+1,beginOr,count);
}

    if(left+1 < endPre && count+1 < endOr){
   root.right=localTree(preorder,inorder,left+1,endPre,count+1,endOr);
   }
    return root;
}

}
时间复杂度O(n)
空间复杂度O(n)
”’

0 赞同 0 条回复

V2ero 普通 2023年7月17日上午10:44

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

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if(!preorder.length || !inorder.length){
        return null;
    }
    // 根节点
    const root = new TreeNode(preorder[0]);
    let rootIndex = inorder.findIndex(v => v === preorder[0]);
    if(rootIndex === -1) return null;
    preorder.shift();
    root.left = buildTree(preorder,inorder.slice(0, rootIndex));
    root.right = buildTree(preorder,inorder.slice(rootIndex+1));

    return root;
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月16日下午11:57

Day9：下面是代码

class Solution {
    int[] preorder;
    HashMap<Integer,Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //将前序遍历数组 preorder 赋值给了当前类的成员变量 this.preorder
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++){
            dic.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }
    //recur中，root为前序遍历中的根节点索引，left和right是中序遍历中的索引。
    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;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月16日下午11:42

/**
 * 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) {
        int n=inorder.length;
        //遍历中序遍历序列
        for(int i=0;i<n;i++){
            //以结点值为key，下标为value
            map.put(inorder[i],i);
        }
        return build(preorder,inorder,0,n-1,0,n-1);
    }

    public TreeNode build(int[] preorder, int[] inorder,int preLeft,int preRight,int inLeft,int inRight){
        if(preLeft>preRight) return null;
        //获取根节点的值
        int rootVal=preorder[preLeft];
        //获取根节点在中序遍历中的下标
        int rootIndex=map.get(rootVal);
        TreeNode root=new TreeNode(rootVal);
        //统计左子树有多少个节点
        int leftTreeNum=rootIndex-inLeft;
        root.left=build(preorder,inorder,preLeft+1,preLeft+leftTreeNum,inLeft,rootIndex-1);
        //统计右子树有多少个节点
        int rightTreeNum=inRight-rootIndex;
        root.right=build(preorder,inorder,preLeft+leftTreeNum+1,preRight,rootIndex+1,inRight);
        return root;
    }
}

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

0 赞同 0 条回复

wonderful 普通 2023年7月16日下午10:42

前序遍历的第一个元素为根节点，在中序遍历中根节点左边为左子树右边为右子树

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None

    root = TreeNode(preorder[0])
    stack = [root]
    inorderIndex = 0
    for i in range(1, len(preorder)):
        preorderVal = preorder[i]
        node = stack[-1]
        if node.val != inorder[inorderIndex]:
            node.left = TreeNode(preorderVal)
            stack.append(node.left)
        else:
            while stack and stack[-1].val == inorder[inorderIndex]:
                node = stack.pop()
                inorderIndex += 1
            node.right = TreeNode(preorderVal)
            stack.append(node.right)

    return root

0 赞同 0 条回复

周小二普通 2023年7月16日下午9:45

class Solution {
    private int[] preorder;
    private Map<Integer, Integer> map = new HashMap<>();

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

    private TreeNode recur(int root, int left, int right) {
        //left 小于 right 表示无此节点
        if (left > right) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        // left 等于right 表示仅有一个节点，无子节点
        if (left == right) {
            return node;
        }
        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 条回复

阿尚普通 2023年7月16日下午7:46

//重建二叉树
class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) return null;
        map = new HashMap<>();
        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 preBegin, int preEnd, int[] inorder, int inBegin, int inEnd){
        if(preBegin > preEnd || inBegin > inEnd) return null;

        int rootVal = preorder[preBegin];
        int rootIdx = map.get(rootVal);
        int leftSize = rootIdx - inBegin;
        TreeNode root = new TreeNode(rootVal);

        root.left = build(preorder, preBegin + 1, preBegin + leftSize, inorder, inBegin, rootIdx - 1);
        root.right = build(preorder, preBegin + leftSize + 1, preEnd, inorder, rootIdx + 1, inEnd);

        return root;
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月16日下午3:32

class Solution {
public:
    TreeNode* buildSubTree(vector<int>& p, vector<int>& i, int pStart, int pEnd, int iStart, int iEnd)
{
    if(iStart >= iEnd){
        return nullptr;
    }
    int rootVal = p[pStart];
    int rootIndex = iStart;
    for(; rootIndex<iEnd; rootIndex++){
        if(i[rootIndex] == rootVal){
            break;
        }
    }
    TreeNode* root = new TreeNode(rootVal);
    root->left = buildSubTree(p,i,pStart+1,rootIndex+1,iStart,rootIndex);
    root->right = buildSubTree(p,i,pStart+rootIndex-iStart+1,pEnd,rootIndex+1,iEnd);
    return root;
}    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = preorder.size();
        return buildSubTree(preorder, inorder, 0, len, 0, len);
    }
};

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

0 赞同 0 条回复

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

共以下 28 个回答

思路

代码

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题取消回复

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

共以下 28 个回答

思路

代码

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题 取消回复

# 回答此问题取消回复