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

题目

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

示例 1:

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

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

解答

同106的解法相似,因此在这里只提供代码.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 创建根节点
        TreeNode* root = build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        return root;
    }
    
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
        // 特判：preStart > preEnd 时，已经没有节点需要处理，返回 NULL
        if (preStart > preEnd) {
            return nullptr;
        }
        
        // 创建当前子树的根节点
        TreeNode* root = new TreeNode(preorder[preStart]);
        
        // 在中序遍历序列中查找当前子树根节点的位置
        int inRootIndex = inStart;
        while (inorder[inRootIndex] != root->val) {
            inRootIndex++;
        }
        
        // 计算当前子树左子树的大小
        int leftTreeSize = inRootIndex - inStart;
        
        // 递归构建当前子树的左子树和右子树
        root->left = build(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, inRootIndex - 1);
        root->right = build(preorder, preStart + leftTreeSize + 1, preEnd, inorder, inRootIndex + 1, inEnd);
        
        // 返回当前子树的根节点
        return root;
    }
};