康瑞部落

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

解题思路：

题意为给定中序遍历和先序遍历，构建二叉树。

可以用递归的方法来做。

先序遍历的第一个节点即为根节点，在中序遍历中找到根节点，中序遍历中的根节点前面的节点即为左孩子树节点，右边的节点即为右孩子树节点。如此递归构造即可。

/**
 * 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) {
        int len = preorder.size();
        if(len==0 || len != inorder.size()){
            return NULL;
        }
        vector<int> leftPre, leftIn;
        vector<int> rightPre, rightIn;
        TreeNode* root = new TreeNode(preorder[0]);
        
        int i=0;
        while(i<len&&inorder[i]!=preorder[0]){
            leftIn.push_back(inorder[i]);
            leftPre.push_back(preorder[i+1]);
            i++;
        }
        i++;
        while(i<len){
            rightIn.push_back(inorder[i]);
            rightPre.push_back(preorder[i]);
            i++;
        }
        root->left = buildTree(leftPre, leftIn);
        root->right = buildTree(rightPre, rightIn);
        
        return root;
    }
};

这里每次都重新构造左孩子树和右孩子树的先序遍历和中序遍历，会导致内存不足。可以用下标来记录当前考虑的下标范围即可。

/**
 * 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) {
        return buildTreeHelper(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
    
    TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd){
        if(preStart>preEnd || inStart>inEnd || (preEnd-preStart)!=(inEnd-inStart)){
            return NULL;
        }
        TreeNode* root = new TreeNode(preorder[preStart]);
        int i=0;
        while(i+inStart<=inEnd && inorder[i+inStart]!= preorder[preStart]){
            i++;
        }
        root->left = buildTreeHelper(preorder, preStart+1, preStart+i, inorder, inStart, inStart+i-1);
        root->right = buildTreeHelper(preorder, preStart+i+1, preEnd, inorder, inStart+i+1, inEnd);
        return root;
    }
};