首页 > 代码库 > Leetcode:Construct Binary Tree 前序和中序、后序和中序构建二叉树

Leetcode:Construct Binary Tree 前序和中序、后序和中序构建二叉树

2024-07-03 19:46:50   228人阅读

前序和中序构建二叉树

后序和中序构建二叉树

分析：主要思路就是 在中序中找根节点然后划分左右子树，具体如下：

1. 查找根节点。 我们知道前序序列的第一个元素 和 后序序列的最后一个元素 肯定是根节点，我们就以此为突破口

2. 确定根节点的坐标。 我们在 中序序列中找到 根节点 的下标。

3. 分割左右子树。

对于中序序列：根节点下标之前的都属于左子树，之后的都属于右子树

对于先序序列：根节点之后的 一段元素(该段长度可以由中序序列的左子树长度确定)属于左子树，左子树之后的元素属于右子树

对于先序序列：根节点之前的 一段元素(该段长度可以由中序序列的右子树长度确定)属于右子树，右子树之后的元素属于左子树

4.对分割好的左右子树递归构建二叉树，注意确定好每段序列的下标范围

例如：

preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}

第一步：查找根节点，对于先序而言，根节点就是第一个元素，也就是7

第二步：确定根节点的坐标，我们在 中序中查找根节点7，确定下标为4

第三步：分割左右子树。

对于中序序列：左子树为 {4, 10, 3, 1}, 右子树为{11, 8, 2}

对于先序序列：左子树为 {10, 4, 3, 1}, 右子树为{2, 8, 11}

注意：任何时候中序序列和先序序列的长度总是相等的。

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return constructTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    
    TreeNode* constructTree(const vector<int>& preorder, int preFirst, int preLast,
                            const vector<int>& inorder, int inFirst, int inLast) {
        int preLen = preLast - preFirst + 1;
        int inLen  = inLast  - inFirst  + 1;
        assert(preLen == inLen && preLen >= 0);
        if (preLen == 0) return nullptr;
        
        TreeNode* root = new TreeNode(preorder.at(preFirst));
        int rootIndex = distance(inorder.begin(), find(inorder.begin(), inorder.end(), preorder.at(preFirst)));
        int leftLen  = rootIndex - inFirst;
        int rightLen = inLast - rootIndex;
        root->left =  constructTree(preorder, preFirst + 1, preFirst + leftLen, inorder, inFirst, rootIndex - 1);
        root->right = constructTree(preorder, preLast - rightLen + 1, preLast, inorder, rootIndex + 1, inLast);
        return root;
    }
};

 

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return constructTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
     TreeNode* constructTree(const vector<int>& inorder, int inFirst, int inLast,
                             const vector<int>& postorder, int postFirst, int postLast) {
        int postLen = postLast - postFirst + 1;
        int inLen  = inLast  - inFirst  + 1;
        assert(postLen == inLen && postLen >= 0);
        if (postLen == 0) return nullptr;
        
        TreeNode* root = new TreeNode(postorder.at(postLast));
        int rootIndex = distance(inorder.begin(), find(inorder.begin(), inorder.end(), postorder.at(postLast)));
        int leftLen  = rootIndex - inFirst;
        int rightLen = inLast - rootIndex;
        root->left =  constructTree(inorder, inFirst, rootIndex - 1, postorder, postFirst, postFirst + leftLen - 1);
        root->right = constructTree(inorder, rootIndex + 1, inLast, postorder, postLast - rightLen, postLast - 1);
        return root;
    }
};

 


联系
我们