根据前序遍历、中序遍历还原二叉树

已知前序遍历和中序遍历如何构造二叉树

设有前序遍历(根->左->右)：3,9,20,15,7
中序遍历(左->根->右)：9, 3, 15, 20, 7

算法设计

1. 前序遍历的第一点为根节点
2. 在中序遍历中，根节点的左边为其左子树，右边为其右子树
根据以上特性，设置算法流程如下:

确认当前节点、左子树、右子树在左子树中递归在右子树中递归功能代码及测试代码

#include 
#include 
#include 
#include 



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* buildTreeUntil( int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        
        if (preorderLeft > preorderRight) {
            
            return nullptr;
        }

        int inorderRoot = m_map[m_preorder[preorderLeft]];/// 当前节点在中序遍历的位置
        TreeNode* root = new TreeNode(m_preorder[preorderLeft]);/// 构建当前节点
        // 计算左子树的大小（根节点在）
        int sizeLeftSubtree = inorderRoot - inorderLeft;
        // 2. 在左子树中递归
        /// 左子树的在前序遍历中的起始位置preorderLeft + 1，终止位置preorderLeft + sizeLeftSubtree 
        /// 左子树在中序遍历的的起始位置 inorderLeft 终止位置inorderRoot - 1
        root->left = buildTreeUntil( preorderLeft + 1, preorderLeft + sizeLeftSubtree, inorderLeft, inorderRoot - 1);
        // 3. 在右子树中递归
        root->right = buildTreeUntil(preorderLeft + sizeLeftSubtree + 1, preorderRight, inorderRoot + 1, inorderRight);
        return root;
    }

    TreeNode* buildTree(std::vector& preorder, std::vector& inorder) {
        int nSize = static_cast(preorder.size());
        // 构建中序遍历的键值对，便于快速搜索
        for (int i = 0; i < nSize; ++i) {
            m_map[inorder[i]] = i;
        }
        m_preorder = preorder;
        //m_inorder = inorder;
        TreeNode* node =buildTreeUntil( 0, nSize - 1, 0, nSize - 1);
        return node;
    }
private:
    std::map m_map;
    std::vector m_preorder;///<前序遍历结果
    //std::vector m_inorder;///<中序遍历结果
};

//前序遍历（根左右）
void DLR(TreeNode* root, std::vector& traversal) {
    if (nullptr!=root)
        traversal.push_back(root->val);
    else 
        return;
    DLR(root->left, traversal);
    DLR(root->right, traversal);
    return;
}

//中序遍历（左根右）
void LDR(TreeNode* root, std::vector& traversal) {
    if (nullptr == root) 
        return;
    LDR(root->left, traversal);
    traversal.push_back(root->val);
    LDR(root->right, traversal);
    return;
}

//后续遍历（左右根）
void LRD(TreeNode* root, std::vector& traversal) {
    if (nullptr== root)
        return;
    LRD(root->left, traversal);
    LRD(root->right, traversal);
    traversal.push_back(root->val);
    return;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::vector preorder = { 3,9,20,15,7 };
    std::vector inorder = {9, 3, 15, 20, 7};
    Solution mSolution;
    TreeNode*  root = mSolution.buildTree(preorder, inorder);
    std::vector result;
    std::cout << "前序遍历（根左右）n";
    DLR(root, result);
    for (auto& it : result)
        std::cout << it << std::endl;
    result.clear();
    std::cout << "中序遍历（左根右）n";
    LDR(root, result);
    for (auto& it : result)
        std::cout << it << std::endl;
    result.clear();
    std::cout << "后序遍历（左右根）n";
    LRD(root, result);
    for (auto& it : result)
        std::cout << it << std::endl;
    result.clear();
    system("pause");
    return 0;
}

根据前序遍历、中序遍历还原二叉树

C/C++/C#相关栏目本月热门文章