来源:力扣(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],返回如下的二叉树:

    3
   / \
  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;
    }
};

执行通过:



最后修改:2020 年 02 月 07 日
喜欢就给我点赞吧