题解 | #重建二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param preOrder int整型vector
     * @param vinOrder int整型vector
     * @return TreeNode类
     */
     //参数解释：begin_preOrder:先序遍历起始索引 end_preOrder:先序遍历序列结尾索引  其余类推
    TreeNode* build_node(vector<int>& preOrder, vector<int>& vinOrder,
                         int begin_preOrder, int end_preOrder, int begin_vinOrder,
                         int end_vinOrder) {
        //递归终止条件  若当前先序遍历索引或中序遍历索引参数 首大于尾 则表示遇到了非全孩子节点 直接返回对应空值
        if (begin_preOrder > end_preOrder || begin_vinOrder > end_vinOrder) {
            return nullptr;
        }
        //根据先序序列的起始索引值  构建二叉树节点
        TreeNode* root = new TreeNode(preOrder[begin_preOrder]);
        int k = begin_vinOrder;
        //找到当前先序遍历节点在中序遍历中的位置
        for (; k <= end_vinOrder; k++) {
            if (vinOrder[k] == preOrder[begin_preOrder]) {
                break;
            }
        }
       //显然，在中序遍历中，k的左侧全为当前节点的左子树，k的右侧为当前节点的右子树
       //故节点k的左子树数目为k-begin_vimOrder,在先序遍历中当前已构造节点（k节点）的左子树索引从begin_preOrder+1开始，至begin_preOrder + k - begin_vinOrder结束
       //确定边界后递归构建当前节点的左子树
        root->left = build_node(preOrder, vinOrder,
                                begin_preOrder + 1, begin_preOrder + k - begin_vinOrder , begin_vinOrder,
                                k - 1);
        //同理类推先序遍历中当前已构造节点的右子树索引起始范围
        //确定边界后递归构建当前节点的右子树
        root->right = build_node(preOrder, vinOrder,
                                  begin_preOrder+k-begin_vinOrder+1, end_preOrder, k + 1, end_vinOrder);
        //每层返回已构建好的节点
        return root;

    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {

        // write code here
        TreeNode* root = build_node(preOrder, vinOrder, 0, preOrder.size() - 1, 0,
                                    vinOrder.size() - 1);
        return root;
    }
};