构造二叉树的实践

一、背景

二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。

二、 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

三、分析

对于任意一颗树而言，前序遍历的形式总是：

[ 根节点，[左子树的前序遍历结果]， [右子树的前序遍历结果] ]，即根节点总是前序遍历中的第一个节点。

而中序遍历的形式总是：

[ [左子树的中序遍历结果]，根节点，[右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

 

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

四、代码

 
class Solution
{
private:
    unordered_map<int, int> customMap;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int preLength = preorder.size();
        int inLength = inorder.size();
        if (preLength != inLength) {
            return nullptr;
        }
 
        for (int i = 0;i < inLength;i++) { // 必须使用中序遍历，存在map中
            customMap[inorder[i]] = i;
        }
        return MyBuildTree(preorder, 0, preLength - 1, inorder, 0, inLength - 1);
    }
 
    TreeNode* MyBuildTree(vector<int>& preorder,int preLeft,int preRight, vector<int>& inorder,int inLeft,int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return nullptr;
        }
        // 前序遍历中的第一个节点就是根节点
        int rootVal = preorder[preLeft];
 
        // 在中序遍历中，定位根节点
        int pIndex = customMap[rootVal];
 
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(rootVal);
        
        // 代入公式，注意左节点生成左子树，右节点生成右子树
        root->left = MyBuildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, inorder, inLeft, pIndex - 1);
        root->right = MyBuildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, inorder, pIndex + 1, inRight);
 
        return root;
    }
 
 
 
};

五、从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

六、分析

这道题和上一题的关键区别是，后序遍历和前序遍历相反，根节点对应的值为 postorder 的最后一个元素。

七、代码

 
class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }
 
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
 
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];
 
        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;
 
        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

参考：

力扣

 东哥带你刷二叉树（构造篇） :: labuladong的算法小抄

力扣