C++之《剑指offer》学习记录（11）：重建二叉树

笔者最近在找工作时，无意间读到了一本名为《剑指offer》的书，粗略翻阅了一下，感觉这将会是一本能让我不再苦恼于笔试和面试“手搓代码”的书。故笔者写下该系列博客记录自己的学习历程，希望能和这本书的读者朋友们一起交流学习心得。
介绍：《剑指Offer：名企面试官精讲典型编程题（第2版）》剖析了80个典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这5个面试要点。
编程题链接：牛客网在线编程_算法面试_面试必刷TOP101 (nowcoder.com)
本博客关键词：重建二叉树

题设

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

这道题需要用到递归的思路，感觉难度还是挺大的，自己一开始写并没有写出来，下面展示《剑指offer》里的解法以及牛客官方的解法。

解法一：来自《剑指offer》

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <exception>
class Solution {
  public:
    TreeNode* Construct(int* startPreOrder, int* endPreOrder, int* startVinOrder,
                        int* endVinOrder) {
        int rootValue = startPreOrder[0];
        TreeNode* root = new TreeNode(rootValue);

        if (startPreOrder == endPreOrder) {
            if (startVinOrder == endVinOrder && *startPreOrder == *startVinOrder) {
                return root;
            } else {
                throw std::runtime_error("Invalid input.");
            }
        }

        int* rootVinOrder = startVinOrder;
        while (rootVinOrder <= endVinOrder && *rootVinOrder != rootValue) {
            ++rootVinOrder;
        }

        if (rootVinOrder == endVinOrder && *rootVinOrder != rootValue) {
            throw std::runtime_error("Invalid input.");
        }

        int leftLength = rootVinOrder - startVinOrder;
        int* leftPreOrderEnd = startPreOrder + leftLength;
        if (leftLength > 0) {
            root->left = Construct(startPreOrder + 1, leftPreOrderEnd, startVinOrder,
                                   rootVinOrder - 1);
        }
        if (leftLength < endPreOrder - startPreOrder) {
            root->right = Construct(leftPreOrderEnd + 1, endPreOrder, rootVinOrder + 1,
                                    endVinOrder);
        }
        return root;

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型vector
     * @param vinOrder int整型vector
     * @return TreeNode类
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.empty() || vinOrder.empty()) {
            return nullptr;
        }

        return Construct(&preOrder[0], &preOrder[preOrder.size() - 1], &vinOrder[0],&vinOrder[vinOrder.size() - 1]);
    }
};

解法的大致思路就是，先根据前序遍历的数组，找到根节点（对于前序遍历来说根节点就对应第一个数）。根据在前序遍历数组里找到的根节点，寻找该根节点在中序遍历里对应的位置，该位置左侧即为根节点的左子树，右侧即为右子树。
递归以上操作，终止条件设置为：当前序遍历和中序遍历的左右索引相等时，返回root。

解法二：牛客解法

class Solution {
  public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.empty() || vinOrder.empty()) {
            return nullptr;
        }
        // 构建根节点
        TreeNode* root = new TreeNode(preOrder[0]);
        for (int i = 0; i < vinOrder.size(); i++) {
            if (preOrder[0] == vinOrder[i]) {
                vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + 1 + i);
                vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);
                root->left = reConstructBinaryTree(leftpre, leftvin);
                vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
                vector<int> rightvin(vinOrder.begin() + i + 1, vinOrder.end());
                root->right = reConstructBinaryTree(rightpre, rightvin);
                break;
            }
        }
        return root;
    }
};

个人认为牛客官方的这个解法更容易理解。
这里需要注意一下vector容器的初始化，例如vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);，这里vinOrder.begin()是一个指向leftvin第一个元素的迭代器，vinOrder.begin() + i是指向第i+1个元素（索引为i）的迭代器。
vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);表示使用VinOrder从起始位置到第i个元素的范围来初始化leftvin，不包括第i+1个元素，也就是不包括索引为i的元素。

原文地址：https://blog.csdn.net/S13352784013/article/details/143079742

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！