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

Miracle· 普通 2023年9月6日下午12:41

/**
* 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* build(const vector &preorder, const vector &inorder, int pre_left, int pre_right, int in_left, int in_right) {
// 左边界超过右边界,说明已经到达底部,遍历完节点了
if(pre_left > pre_right) return nullptr;
// 前序遍历中的第一个节点为根节点
int pre_root = pre_left;
// 在中序遍历中找到根节点的索引位置
int in_root = index[preorder[pre_root]];
// 构造根节点
TreeNode root = new TreeNode(preorder[pre_root]);
// 左子树的节点数量
int left_size = in_root – in_left;
// 递归构造左子树并连接到根节点
// 先序遍历中从左边界+1开始的left_size的元素对应了中序遍历中,从左边界到根节点索引-1的元素
root->left = build(preorder, inorder, pre_left + 1, pre_left + left_size, in_left, in_root – 1);
// 递归构造右子树,并连接到根节点
// 先序遍历中从左边界+left_size + 1开始到右边界的元素对应了中序遍历中,从根节点索引+1到右边界的元素
root->right = build(preorder, inorder, pre_left + left_size + 1, pre_right, in_root + 1, in_right);
return root;
}
TreeNode buildTree(vector& preorder, vector& inorder) {
int n = preorder.size();
// 构造哈希表,记录inorder中节点所在位置
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return build(preorder, inorder, 0, n – 1, 0 , n – 1);
}
};

0 赞同 0 条回复

小肸永久会员 2023年8月28日下午2:47

class Solution {
    //时间复杂度为O(N):树有多少节点就递归多少次，每一次递归的时间复杂度为O(1)。
    //空间复杂度为O(N)。
    static Map<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);
        }
        int len = preorder.length;
        return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1);
    }
    TreeNode buildTreeCore(int[] preorder, int pLeft, int pRight, 
                        int[] inorder, int iLeft, int iRight) {
        if (pLeft > pRight || iLeft > iRight) {
            return null;
        }                    
        TreeNode root = new TreeNode(preorder[pLeft]);
        int rootIndex = map.get(root.val);
        //rootIndex - iLeft为左子树的节点数量
        root.left = buildTreeCore(preorder, pLeft + 1, pLeft + (rootIndex - iLeft),
                                inorder, iLeft, rootIndex - 1);
        root.right = buildTreeCore(preorder, pLeft + (rootIndex - iLeft) + 1, pRight,
                                inorder, rootIndex + 1, iRight);
        return root;
    }
}

0 赞同 0 条回复

sincere 普通 2023年8月27日下午9:37

思路：1、前序的第一个是根节点；2、中序里根节点左侧是左子树，右侧是右子树；3、中序里左子树的长度，即为前序中根节点后面的左子树长度。所以可以用一个全局map存储中序节点值和下标的映射，通过不断获取根节点、左右子节点构建树，结束条件就是下标开始值超过下标结束值，此时肯定遍历完了
复杂度：时间复杂度O(n)，空间复杂度O(n)

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 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;
        }
        // 找到 root 的值构建根节点
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        // 找到 root 在中序的索引下标，来确定左右子树长度
        int rootIndex = map.get(rootVal);
        int leftSize = rootIndex - inStart;
        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;
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月27日下午5:51

前面201个用例都够了，第202/203只说是该方法时间超时，但是不太服，只想看是否通过。

/**
 * 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* buildTree(vector& preorder, vector& inorder) {
        if(preorder.empty()){
            return NULL;
        }
        TreeNode* root = new TreeNode(preorder[0]);
        vector inleft;
        vector inright;
        bool partition_left = true;
        for(int i=0; ival){
                if(partition_left){
                    inleft.push_back(inorder[i]);
                    continue;
                }else{
                    inright.push_back(inorder[i]);
                }
            }else{
                partition_left = false;
            }
        }
        vector preleft;
        vector preright;
        for(int i=0; ileft = buildTree(preleft,inleft);
        root->right =  buildTree(preright, inright);
        return root;
    }
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月26日下午11:36

时间复杂度空间复杂度不会算
自己开始的思路是直接在buildTree高数上进行递归操作，但是引出来的问题是每次传参的时候都需要new int[]，导致内存明显浪费。
答案的思路占用空间更小，有对比才能明白这种思路的优势！
根据答案思路写一遍

class Solution {
    HashMap<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] midorder) {
        if(preorder == null || preorder.length == 0) return null;

        map = new HashMap<>();
        for(int j=0; j<midorder.length; j++) {
            map.put(midorder[j], j);
        }

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

    TreeNode f(int[] preorder, int l1, int r1, int l2, int r2) {
        if(r1 > l1 || l2 > r2) return null;

        TreeNode root = new TreeNode(preorder[l1]);
        int index = map.get(preorder[l1]);
        root.left = f(preorder, l1+1, index-l2+l1, l2, index-1);
        root.right = f(preorder, index-l2+l1+1, r1, index+1, r2);
        return root;
    }
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月23日上午11:33

时间o(n), 空间o(n)
class Solution {
public:
    // 字典用于 值->索引 的映射；索引为中序数组中的（因为没有重复的值）
    unordered_map<int, int> map;

    // l1、r1表示前序遍历的左右两端；l2、r2表示中序遍历的两端
    TreeNode* build(vector<int> preorder, vector<int> inorder, int l1, int r1, int l2, int r2){
        if(l1 > r1 || l2 > r2) return NULL;

        // 创建根节点
        int val = preorder[l1];
        TreeNode* rootNode = new TreeNode(val);
        // 在中序数组中找到当前子树 root 的位置
        int i = map[val];

        // 子树在前序和中序数组的长度应该一致
        // r2 - (i+1) = r1 - x
        rootNode->left = build(preorder, inorder, l1+1, i-l2+l1, l2, i-1);
        rootNode->right= build(preorder, inorder, r1-r2+i+1, r1, i+1, r2);

        return rootNode;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for(int i=0; i<n; i++){
            map[inorder[i]] = i;
        }

        TreeNode* root = build(preorder, inorder, 0, n-1, 0, n-1);

        return root;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月21日下午11:53

递归思想：通过前序遍历序列可以得到根节点的值，再通过中序遍历序列可以得到左右子树自己的前序和中序遍历序列，然后递归创建，终止条件是序列为空
时间复杂度O(n)，空间复杂度O(n);

class Solution {
public:
    TreeNode* buildTreeNode(vector& preorder, int l1, int r1, vector& inorder, int l2, int r2) {
        if (l1 > r1 || l2 > r2) {
            return nullptr;
        }
        TreeNode* node = new TreeNode(preorder[l1]);

        node->left = buildTreeNode(preorder, l1 + 1, l1 + m[preorder[l1]] - l2, inorder, l2, m[preorder[l1]] - 1);
        node->right = buildTreeNode(preorder, l1 + 1 + m[preorder[l1]] -l2, r1, inorder, m[preorder[l1]] + 1, r2);

        return node;
    }

    TreeNode* buildTree(vector& preorder, vector& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            m[inorder[i]] = i;
        }

        return buildTreeNode(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    std::map m;
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月21日下午10:49

//重建二叉树
class Solution {
public:
    unordered_map<int,int> mp; //用于寻找下标
    TreeNode* Build(vector<int>& preorder, int l1,int r1,vector<int>& inorder,int l2,int r2)
    {
        if(l1>r1||l2>r2) return NULL;
         TreeNode* root = new TreeNode(preorder[l1]);
         int i=mp[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;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
       for(int i=0;i<inorder.size();++i)
       {
           mp[inorder[i]]=i;
       }
        return Build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月21日下午9:58

1、递归

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int len = preorder.length;
        for(int i=0; i<len; i++){
            if(inorder[i] == preorder[0]){
                root.left = buildTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i));
                root.right = buildTree(Arrays.copyOfRange(preorder, i+1, len), Arrays.copyOfRange(inorder, i+1, len));
            }
        }
        return root;
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月21日下午6:04

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return true;
        }
        return f(postorder, 0, postorder.length -1);

    }

    //递归判断是否符合后序遍历的性质
    public boolean f(int[] postorder, int l, int r) {
        if (l >= r) {
            return true;
        }
        int tag = postorder[r];
        int rightMinPos = -1;
        //第一个大于tag的，一定是右子树最小的那一个或者直接只有右子树
        for (int i = l; i < r; i++) {
            if (postorder[i] > tag) {
                rightMinPos = i;
                break;
            }
        }
        //只有左子树
        if (rightMinPos == -1) {
            return f(postorder, l, r - 1);
        }
        for (int i = rightMinPos + 1; i < r; i++) {
            if (postorder[i] < postorder[r]) {
                return false;
            }
        }

        return f(postorder, l, rightMinPos -1) && f(postorder, rightMinPos, r -1);
    }

}

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复