【二叉树专题】剑指 Offer 07. 重建二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

岱永久会员 2024年12月28日下午7:54

class Solution {
    HashMap<Integer,Integer> map = new HashMap<>();
    int[] preorder;//保留的先序遍历，方便递归时依据索引查看先序遍历的值
    public TreeNode deduceTree(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 条回复

mpweixin用户普通 2024年12月23日下午5:29

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return NULL;
        TreeNode* root = new TreeNode(preorder[0]);
        if(preorder.size() == 1) return root;
        int it = 0;
        for(;it<inorder.size();it++){
            if(inorder[it] == preorder[0]) break;
        }
        vector<int> leftinorder(inorder.begin(), inorder.begin()+it);
        vector<int> rightinorder(inorder.begin()+it+1, inorder.end());
        vector<int> leftpreorder(preorder.begin()+1, preorder.begin()+1+leftinorder.size());
        vector<int> rightpreorder(preorder.begin()+1+leftinorder.size(), preorder.end());
        root->left = deduceTree(leftpreorder, leftinorder);
        root->right = deduceTree(rightpreorder, rightinorder);
        return root;

    }
};

递归：
1. 数组为空返回NULL，数组仅一个元素返回root
2. 根据前序第一个元素的值，切割中序数组
3. 递归左右子树，最后整体返回。

0 赞同 0 条回复

youngsir 普通 2024年12月10日上午11:09

根据前序遍历和中序遍历的性质

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,inorder,0,0,inorder.size()-1);
    }
    TreeNode* build(vector<int>& preorder,vector<int>& inorder,int root,int start,int end ){
        if(start > end) return nullptr;
        TreeNode * tree = new TreeNode(preorder[root]);
        int i = start;
        while(i<end && preorder[root] != inorder[i]) i++;
        tree->left = build(preorder,inorder,root + 1,start,i-1);
        tree->right = build(preorder,inorder,root + 1+i-start,i+1,end);
        return tree;

    }
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月5日下午11:27

解题思路
前序遍历：第一个节点一定就是根节点
中序遍历：根节点左边的数据全部都是左子树，右边的数据全部都是右子树
后序遍历：最后一个节点一定就是根节点
题目给了前序+中序，可以根据前序获取根节点，拉着根节点去中序里面拆分左右子树，然后继续通过递归找出左右子树的根节点。
题解1【不推荐解法】拆分了原本的2个数组，空间浪费了，其实不需要拆分

class Solution {


    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        // head的value
        int headValue=preorder[0];
        // 【错误点1】
        // 找到inorder中头结点的坐标(数据是不重复的)
        int middleIndex = 0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==headValue){
                middleIndex=i;
                break; 
            }
        }

        // 进行数组的拆分
        // 拆分inorder
        int[] inorderLeft = split(inorder, 0, middleIndex - 1);
        int[] inorderRigth = split(inorder, middleIndex + 1, inorder.length - 1);
        // 拆分preorder
        int[] preorderLeft = split(preorder, 1, inorderLeft.length);
        int[] preorderRigth = split(preorder, inorderLeft.length + 1, inorder.length - 1);
        // preorder的第一个节点作为头结点
        TreeNode head = new TreeNode(headValue);
        head.left = deduceTree(preorderLeft, inorderLeft);
        head.right = deduceTree(preorderRigth, inorderRigth);
        return head;
    }

    public int[] split(int[] source, int beginIndex, int endIndex) {
        int[] target = new int[endIndex - beginIndex + 1];
        int j = 0;
        for (int i = 0; i < source.length; i++) {
            if (i >= beginIndex && i <= endIndex) {
                target[j++] = source[i];
            }
        }
        return target;
    }
}

错误点1：以为左右子树的个数是相等的，结果就去/2取值，实际上左右子树的个数是不相等的，需要通过number去找到index

题解2【不去拆分数组，并且使用Map去缓存number对应的index】

class Solution {

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

    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        // 找到inorder中头结点的坐标(数据是不重复的)
        // 构建Map<inNumber，index>的缓存
        for (int i = 0; i < inorder.length; i++) {
            inNumber2IndexMap.put(inorder[i], i);
        }
        // 【错误点1】
        /**
         * 不需要额外计算一遍
         * // 找到head的value在inorder的位置
         * int headValue = preorder[0];
         * int middleIndex = inNumber2IndexMap.get(headValue);
         * // 进行数组的拆分
         * // preorder的第一个节点作为头结点
         * TreeNode head = new TreeNode(headValue);
         * head.left = deduceChildTree(preorder, 1, middleIndex, inorder, 0, middleIndex
         * - 1);
         * head.right = deduceChildTree(preorder, middleIndex + 1, preorder.length - 1,
         * inorder, middleIndex + 1,
         * inorder.length - 1);
         * return head;
         */
        return deduceChildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode deduceChildTree(int[] preorder, int prebeginIndex, int preendIndex, int[] inorder, int inbeginIndex,
            int inendIndex) {
        // 只有1个节点时会出现这种情况
        if (prebeginIndex > preendIndex || inbeginIndex > inendIndex) {
            return null;
        }
        if (prebeginIndex == preendIndex) {
            return new TreeNode(preorder[prebeginIndex]);
        }
        int headValue = preorder[prebeginIndex];
        int middleIndex = inNumber2IndexMap.get(headValue);
        // 【错误点2】计算左子树的大小，可以简化表达式
        int leftSize = middleIndex - inbeginIndex;
        TreeNode head = new TreeNode(headValue);
        // 【错误点3】之前用的是middleIndex当做了长度，但是当区间发生变化了，就不能作为长度了
        head.left = deduceChildTree(preorder, prebeginIndex + 1, prebeginIndex + leftSize, inorder,
                inbeginIndex, middleIndex - 1);
        head.right = deduceChildTree(preorder, prebeginIndex + leftSize + 1, preendIndex, inorder,
                middleIndex + 1,
                inendIndex);
        return head;
    }

}

错误点1：抽象出了deduceChildTree方法之后，在原方法就没必要单独写一遍，而是作为特例调用deduceChildTree即可
错误点2：通过一些临时变量，可以让整个代码变得更加简洁和可理解。
错误点3：middleIndex当做了长度的衡量，第一次遍历起始index=0，所以没有错误，但是后续起始index发生变化了，middleIndex就不能作为长度衡量的标准了。

1 赞同 0 条回复

休一普通 2024年12月4日下午2:34

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        //首先进行防御性编程
        if(preorder.empty() || inorder.empty()) return nullptr;
        //进行递归恢复树的结构
        return recoverTree(preorder, inorder);
    }

    TreeNode* recoverTree(vector<int>& preorder, vector<int>& inorder)
    {
        //1.首先根据前序数组确定中节点
        if(preorder.empty()) return nullptr;
        int centerValue = preorder[0];
        TreeNode* root = new TreeNode(centerValue);
        //然后在中序数组中找到头节点来分割左右子树
        int index = 0;
        for(;;index++)
        {
            if(inorder[index] == centerValue) break;
        }
        //构建左右子树的中序数组
        vector<int> childInorderLeft(inorder.begin(),inorder.begin()+index);
        vector<int> childInorderRight(inorder.begin()+index+1,inorder.end());
        //构建左右子树的前序数组
        vector<int> childPreorderLeft(preorder.begin()+1,preorder.begin()+1+childInorderLeft.size());
        vector<int> childPreorderRight(preorder.begin()+1+childInorderLeft.size(),preorder.end());
        //递归构建树结构
        root->left = recoverTree(childPreorderLeft, childInorderLeft);
        root->right = recoverTree(childPreorderRight, childInorderRight);
        return root;
    }
};

0 赞同 0 条回复

Tom Yuan 普通 2024年12月4日下午1:50

方法：通过找到root在两次遍历结果间的位置关系来确定左右子树的长度/元素和顺序。
注意root_pos – l2 是左边子树的长度，这点比较容易弄错。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        map = {}
        for i in range(len(inorder)):
            map[inorder[i]] = i

        def f(preorder, l1, r1, inorder, l2, r2):
            if l1 > r1 or l2 > r2:
                return None
            root = TreeNode(preorder[l1])
            root_pos = map[root.val]
            # root_pos - l2: length of left subtree
            root.left = f(preorder, l1 + 1, l1 + root_pos - l2, inorder, l2, root_pos - 1)
            root.right = f(preorder, l1 + root_pos - l2 + 1, r1, inorder, root_pos + 1, r2)
            return root

        return f(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)

time O(n) space O(n)
需要再多画图加深一下理解

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午9:43

根据中序遍历及前序遍历，确认各个节点的对应关心

class Solution {
    int []preorder;
    HashMap<Integer,Integer>hmap=new HashMap<>();
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        for(int i=0;i<inorder.length;i++)hmap.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=hmap.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 条回复

晓宇普通 2024年12月2日下午5:10

class Solution {
public:

    unordered_map<int, int> map;
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        for(int i = 0;i < inorder.size();i++){
            map[inorder[i]] = i;
        }
        return f(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode* f(vector<int>& preorder,int l1, int r1,vector<int>& inorder, int l2, int r2){
        if(l1 > r1 && l2 > r2) return nullptr;
        TreeNode *root = new TreeNode(preorder[l1]);
        int i = map[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;

    }
};
// 思路：递归。
（1）确定根节点，前序遍历的首位节点；
（2）确定左右子树。由中序遍历和前序遍历确认；
（3）确定子问题。确认各级左右子树。确定递归的边界条件（该节点无左右节点）。
（4）返回根节点root。
// 时间复杂度：o(n) ；空间复杂度：o(n)

0 赞同 0 条回复

Aatorx 永久会员 2024年12月2日下午4:41

class Solution {
public:
    unordered_map<int,int> map;
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() && inorder.empty()){
            return nullptr;
        }
        for (int i=0; i < inorder.size(); i++){
            map[inorder[i]] = i;
        }
        return recur(preorder, 0, 0, preorder.size()-1);
    }
    TreeNode* recur(vector<int> preorder, int root, int l, int r){
        if(l > r){
            return nullptr;
        }
        TreeNode* temp = new TreeNode(preorder[root]);
        int m = map[preorder[root]];
        temp->left = recur(preorder, root + 1, l, m-1);
        temp->right = recur(preorder, root + m - l + 1, m + 1, r);
        return temp;
    }
};

递归时只需要记录preorder数组的左右子树根节点位置以及inorder数组左右子树的范围。分别用root，l，r表示。利用哈希表可以很方便的找到分界点。因为preorder数组是前序遍历的结果，所以左子树的根节点为root+1。右子树的根节点为root+左子树的长度+1。
时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

Jerry 普通 2024年12月1日下午9:43

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeHelper(preorder,0,preorder.size()-1, inorder, 0, inorder.size()-1);
    }
    TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd,
                             vector<int>& inorder, int inStart, int inEnd){
        if(preStart > preEnd || inStart > inEnd){
            return nullptr;
        }
        if(preStart == preEnd && inStart == inEnd){
            TreeNode* node = new TreeNode(preorder[preStart]);
            return node;
        }
        int rootval = preorder[preStart];
        int rootindex = -1;
        for(int i = inStart; i <= inEnd; i++){
            if(inorder[i] == rootval){
                rootindex = i;
            }
        }
        int preindex = preStart + (rootindex - inStart);
        TreeNode* root = new TreeNode(preorder[preStart]);
        TreeNode* leftchild = buildTreeHelper(preorder, preStart+1, preindex,
                                             inorder, inStart, rootindex-1);
        TreeNode* rightchild = buildTreeHelper(preorder, preindex+1, preEnd,
                                            inorder, rootindex+1, inEnd);
        root->left = leftchild;
        root->right = rightchild;
        return root;
    }
};

时间o(n)
空间o(n)
错误点注意：
这里需要注意：int preindex = preStart + (rootindex - inStart);
刚开始写的是：int preindex = preStart + rootindex;是不对的，rootindex只是恰好在本题第一个测试用例代表了左子树的node个数，一旦inStart！=0，则无法代表左子树的node个数了，会fail，此处需要注意！

0 赞同 0 条回复

遇事不决睡大觉普通 2024年12月1日下午6:09

/**
* 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 {
int[] preorder;
HashMap<Integer, Integer> hmap = new HashMap<>();

public TreeNode deduceTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    for (int i = 0; i < inorder.length; i++) {
        hmap.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 = hmap.get(preorder[root]);
    node.left = recur(root + 1, left, i - 1);
    node.right = recur(root + i - left + 1, i + 1, right);
    return node;
}

}//用map记录preorder和inorder之间的关系

0 赞同 0 条回复

Xiang. 永久会员 2024年12月1日上午9:52

class Solution {
    Map<Integer, Integer> map = new HashMap<>(); // 存储中序数组的值与位置信息

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

    public TreeNode deduce(int[] preorder,int l1,int r1,int[] inorder,int l2,int r2){
        if(l1>r1||l2>r2) return null;
        int tmpVal=map.get(preorder[l1]);  //中序数组前半部分：[l2,tmpVal-1] 后半部分：[tmpVal+1,r2]
        TreeNode root=new TreeNode(preorder[l1]);
        root.left=deduce(preorder,l1+1,l1+tmpVal-l2,inorder,l2,tmpVal-1);
        root.right=deduce(preorder,l1+tmpVal-l2+1,r1,inorder,tmpVal+1,r2);
        return root;
    }
}
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

Kisara 普通 2024年11月30日下午7:18

先序的头是根节点，再中序中找到根节点，然后递归构建二叉树

/**
 * 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 {
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        return build(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }

    public TreeNode build(int[] preorder,int[] inorder,int preStart,int preEnd,int inoStrat,int inoEnd){
        if(preStart>preEnd||inoStrat>inoEnd) return null;

        int val=preorder[preStart];
        TreeNode node=new TreeNode(val);
        int index=0;
        for(int i=inoStrat;i<=inoEnd;i++){
            if(inorder[i]==val){
                index=i;
                break;
                }
        }

        int leftsize=index-inoStrat;

        node.left=build(preorder,inorder,preStart+1,preStart+leftsize,inoStrat,index-1);
        node.right=build(preorder,inorder,preStart+leftsize+1,preEnd,index+1,inoEnd);

        return node;
    }
}

补充一个中序后序建立二叉树的题目

/**
 * 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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(postorder, inorder, 0, postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode build(int[] postorder, int[] inorder, int postStart, int postEnd, int inoStart, int inoEnd) {
        if (postStart > postEnd || inoStart > inoEnd) return null;

        // 后序遍历的根节点是 postEnd 索引位置的值
        int val = postorder[postEnd];
        TreeNode node = new TreeNode(val);

        // 在中序遍历中找到根节点的位置
        int index = 0;
        for (int i = inoStart; i <= inoEnd; i++) {
            if (inorder[i] == val) {
                index = i;
                break;
            }
        }

        // 左子树的大小是根节点在中序遍历中的位置减去起始位置
        int leftSize = index - inoStart;

        // 构建左子树
        node.left = build(postorder, inorder, postStart, postStart + leftSize - 1, inoStart, index - 1);
        // 构建右子树
        node.right = build(postorder, inorder, postStart + leftSize, postEnd - 1, index + 1, inoEnd);

        return node;
    }
}

On ON

0 赞同 0 条回复

苯庸普通 2024年11月30日下午6:29

class Solution {
HashMap<Integer, Integer> inMap = new HashMap();
int[] preorder;
public TreeNode deduceTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0; i < inorder.length; i++){
inMap.put(inorder[i], i);
}
return build(0, 0, inorder.length-1);
}

TreeNode build(int preRoot, int in_left, int in_right){
    if(in_left > in_right) return null;
    TreeNode root = new TreeNode(preorder[preRoot]);
    int idx = inMap.get(preorder[preRoot]);
    root.left = build(preRoot + 1, in_left, idx - 1);
    root.right = build(preRoot + (idx - in_left + 1), idx + 1, in_right);
    return root;
}

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Renasc 普通 2024年11月30日下午3:38

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

class Solution {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length <= 0) {
            return null;
        }

        // 建立中序元素-下标映射
        for (int i=0; i<inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

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

        return root;
    }

    public 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 index = inorderMap.get(preorder[l1]);

        // 开始递归建立左右子树
        root.left = f(preorder, l1+1, l1+(index-l2), inorder, l2, index-1);
        root.right = f(preorder, l1+(index-l2)+1, l2, inorder, index+1, r2);

        return root;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年11月30日下午2:16

//先序遍历第一个节点一定是根结点，找到跟节点在中序遍历中的位置，左边是根结点左子树，右边为右子树，递归构建树，时间复杂度和空间复杂度都是O(N).
class Solution {
private Map<Integer, Integer> inorderIndexMap;
private int preorderIndex;
public TreeNode deduceTree(int[] preorder, int[] inorder) {
inorderIndexMap = new HashMap<>();
preorderIndex = 0;
for (int i = 0; i < inorder.length; i++) {
inorderIndexMap.put(inorder[i], i);
}

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

public TreeNode buildTree(int[] preorder, int startNum , int endNum) {
    if (startNum > endNum) return null;

    int rootVal = preorder[preorderIndex++];
    TreeNode rooTreeNode = new  TreeNode(rootVal);

    int rootIndex = inorderIndexMap.get(rootVal);

    rooTreeNode.left = buildTree(preorder, startNum, rootIndex -1);
    rooTreeNode.right = buildTree(preorder, rootIndex +1, endNum);

    return rooTreeNode;
}

}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午12:57

/**
 解题思路：
 先序遍历数组第一个元素为根节点，余下元素的左右子树归属需要根据中序遍历结果确定,
 如果先序数组根元素的值为x, 则中序数组中值为x左侧元素则属于左子树，x右侧则属于右子树, 根据左右子树的节点数，找到先
 序遍历中的左子树部分和中序遍历的左子树部分递归构造，右子树同理

 依次遍历先序数组，每个元素均需要查找在中序数组的位置，进行构造，复杂度 O(N ** 2)

 优化：可提前将中序数组的 value和index存储到哈希表中，每次查找复杂度为O(1), 整体复杂度为O(N)
 */
class Solution {

    int[] preorder = null;
    int[] inorder = null;

    Map<Integer, Integer> inorderIdx = null;

    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0 || inorder.length != preorder.length){
            return null;
        }
        this.preorder = preorder;
        this.inorder = inorder;
        this.inorderIdx = new HashMap<>();
        for (int i = 0; i < inorder.length; i++){
            inorderIdx.put(inorder[i], i);
        }
        return construct(0, preorder.length-1, 0, inorder.length-1, inorder.length);
    }

    public TreeNode construct(int pStart, int pEnd, int iStart, int iEnd, int size){
        if (size == 0){
            return null;
        }
        int rval = preorder[pStart];
        TreeNode root = new TreeNode(rval);

        // int midInd = 0;
        // for (int i = iStart; i <= iEnd; i++){
        //     if (rval == inorder[i]){
        //         midInd = i;
        //     }
        // }

        int midInd = inorderIdx.get(rval);

        int leftSize = midInd - iStart;
        root.left = construct(pStart + 1, pStart + leftSize, iStart, midInd - 1, leftSize);
        root.right = construct(pStart + leftSize + 1, pEnd, midInd + 1, iEnd, size - leftSize - 1);
        return root;
    }


}

0 赞同 0 条回复

迢迢星野普通 2024年11月29日下午10:50

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        // 前序遍历：根 左 右 
        // 中序遍历：左 根 右
        // 根据中序遍历来划分左右子树，使用 HashMap 记录中序遍历元素 -> 元素索引
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }

        // 构建二叉树
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        // 越界判断
        if (preStart > preEnd) {
            return null;
        }

        // 确定根节点的值
        int rootVal = preorder[preStart];
        // 获取根节点的索引
        int rootIndex = valToIndex.get(rootVal);
        // 计算左子树的长度
        int leftSize = rootIndex - inStart;

        // 创建根节点
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
        return root;
    }
}

思路：记录中序遍历序列及其索引的映射，用于后续计算左子树长度使用，确定左右子树的区间。递归的构建二叉树。
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

jaron 普通 2024年11月29日下午10:28

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

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

    public TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {
        if (l1 > r1 || l2 > r2) {
            return null;
        }
        // 前序的第一个是根节点
        TreeNode head = new TreeNode(pre[l1]);
        if (l1 == r1) {
            return head;
        }
        // 没有重复，所以从中序找到根节点位置
        int k = map.get(pre[l1]);
        // pre : l1(........)[.......r1]
        // in : (l2......)k[........r2]
        // (...)是左树对应，[...]是右树的对应
        head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
        head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
        return head;
    }
}

0 赞同 0 条回复

lQl 永久会员 2024年11月29日下午9:56

递归,重点是边界的划定

class Solution {
    int[] preorder;
    HashMap<Integer,Integer> hashmap = new HashMap<>();
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0;i<inorder.length;i++){
            hashmap.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 newNode = new TreeNode(preorder[root]);
        int i = hashmap.get(preorder[root]);
        newNode.left = recur(root+1,left,i-1);
        newNode.right = recur(root+i-left+1,i+1,right);
        return newNode;
    }
}

0 赞同 0 条回复

黑键〰普通 2024年11月29日下午9:03

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var deduceTree = function(preorder, inorder) {
    if(preorder == null || preorder.length <= 0) return null
    let map = new Map()
    for(let i=0; i<inorder.length; i++) {
        map.set(inorder[i], i)
    }
    let root = buildTree(map, preorder, 0, preorder.length-1, inorder, 0, inorder.length-1)
    return root
};

const buildTree = (map, pre, l1, r1, ino, l2, r2) => {
    if(l1 > r1 || l2 > r2) {
        return null
    }
    let root = new TreeNode(pre[l1])
    // 拿到根节点在中序遍历的下标
    let i = map.get(pre[l1])
    root.left = buildTree(map, pre, l1+1, l1+i-l2, ino, l2, i-1)
    root.right = buildTree(map, pre, l1+i-l2+1, r1, ino, i+1, r2)
    return root
}

思路：看完讲解视频之后写出来的。主要就是碰到这类问题的时候，没有思路或者怕理不清的时候，一定要画图
画图标注下标，一步步推理，可以看出来结论和规律，然后进行递归

0 赞同 0 条回复

秋山丽奈普通 2024年11月29日下午7:50

思路：先序遍历首先遍历到的结点为父节点，并在中序遍历中找到对应节点位置，中序结点左侧即为左子树结点，中序结点右侧即为右子树结点，递归构造即可

class Solution {

    public int[] preUse ;
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        // 先序遍历 获得 头节点 
        // 中序遍历 获得 子树
        preUse = new int[preorder.length];

        TreeNode root = new TreeNode();
        root.val = preorder[0];
        preUse[0] = 1;

        // 找到子节点在中序遍历中的位置 
        int indexOfRoot = 0;
        while(root.val != inorder[indexOfRoot]){
            indexOfRoot ++;
        }

        // 构造 子数组 
        int[] leftTree = null;
        if(indexOfRoot != 0){
            leftTree = Arrays.copyOfRange(inorder, 0, indexOfRoot);
        }

        int[] rightTree = null;
        if(inorder.length - 1 > indexOfRoot){
            rightTree = Arrays.copyOfRange(inorder, indexOfRoot + 1, inorder.length);
        }

        TreeNode leftNode = null;
        TreeNode rightNode = null;
        if(leftTree != null){
            leftNode = buildMyTree(preorder, leftTree);
        }
        if(rightTree != null){
            rightNode = buildMyTree(preorder, rightTree);
        }

        root.left = leftNode;
        root.right = rightNode;

        return root;

    }

    public TreeNode buildMyTree(int[] preorder, int[] inorder){

        if(inorder == null){
            return null;
        }

        if(inorder.length == 1){
            // 到达叶子节点 构造
            // System.out.println("tree node! " + inorder[0]);
            TreeNode node = new TreeNode();
            node.val = inorder[0];
            node.left = null;
            node.right = null;

            int index = 0;
            while(node.val != preorder[index]){
                index ++;
            }
            preUse[index] = 1;

            return node;
        }

        TreeNode node = new TreeNode();

        // 使用 前缀 获得当前 结点 
        int index = 0;
        while(preUse[index] != 0){
            index ++;
        }

        node.val = preorder[index];
        preUse[index] = 1;

        // System.out.println("node val: " + node.val );

        int indexOfRoot = 0;
        while(node.val != inorder[indexOfRoot]){
            indexOfRoot ++;
        }


        // 构造 子数组 
        int[] leftTree = null;
        if(indexOfRoot != 0){
            leftTree = Arrays.copyOfRange(inorder, 0, indexOfRoot);
        }

        int[] rightTree = null;
        if(inorder.length - 1  > indexOfRoot){
            rightTree = Arrays.copyOfRange(inorder, indexOfRoot + 1, inorder.length);
        }

        TreeNode leftNode = null;
        TreeNode rightNode = null;
        if(leftTree != null){
            leftNode = buildMyTree(preorder, leftTree);
        }
        if(rightTree != null){
            rightNode = buildMyTree(preorder, rightTree);
        }

        node.left = leftNode;
        node.right = rightNode;

        return node;
    }
}

0 赞同 0 条回复

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

共以下 22 个回答

# 回答此问题取消回复

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

共以下 22 个回答

# 回答此问题 取消回复

# 回答此问题取消回复