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

马谦马谦马谦

615
文章

17
评论

2020 年 2 月 7 日 23:31:14数据结构和算法评论233字数 489阅读 1 分 37 秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出前序遍历 preorder = [3,9,20,15,7]，中序遍历 inorder = [9,3,15,20,7]，返回如下的二叉树：

/ \

9 20

/ \

15 7

二、题解

这道题在《剑指 offer 》也出现了，题目完全一样。主要用到了树的两个特性：

前序遍历的首元素为根节点。
中序遍历中，根节点的左边是左子树，根节点的右边是右子树。

解题的思路就是：通过前序遍历得到根节点，然后在中序遍历中找到这个节点，再通过递归的方式找出左右子树。

详细的分析可以参考《剑指 offer 》面试题 7：重建二叉树。

三、代码：

/**
 * 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) {
        size_t len = preorder.size();
        if (len < 1)
            return nullptr;
        return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1);        
    }
private:
    TreeNode *buildTreeCore(vector<int> &preOrder, unsigned int preStart, unsigned int preEnd,
                            vector<int> &inOrder, unsigned int inStart, unsigned int inEnd) {
        unsigned int idx, lchild_len;
        TreeNode *root = nullptr;
        root = new TreeNode(preOrder[preStart]);

        if (preStart == preEnd) {
            return root;
        }

        // 在中序遍历中找到根节点
        idx = inStart;
        while (idx < inEnd && root->val != inOrder[idx]) {
            idx++;
        }

        // 左子树的长度
        lchild_len = idx - inStart;
        
        if (lchild_len > 0) {
            // 计算左子树
            root->left = buildTreeCore(preOrder, preStart + 1, preStart + lchild_len,
                    inOrder, inStart, idx - 1);
        }

        if (lchild_len < preEnd - preStart) {
            // 计算右子树
            root->right = buildTreeCore(preOrder, preStart + lchild_len + 1, preEnd,
                    inOrder, idx + 1, inEnd);
        }

        return root;
    }
};