面试题7：重建二叉树

Java版本：

public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	public TreeNode(int val) {
		// TODO Auto-generated constructor stub
		this.val = val;
	}
}

public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		if (pre.length == 0 || in.length == 0) {
			return null;
		}
		// 前序遍历的第一个结点是根节点
		TreeNode root = new TreeNode(pre[0]);
		for (int i = 0; i < in.length; i++) {
			// 在中序遍历中找到前序的根节点
			if (in[i] == pre[0]) {
				// 创建左子树
				root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
				// 创建右子树
				root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
						Arrays.copyOfRange(in, i + 1, in.length));
				break;
			}
		}
		return root;
}

C++版本：

#include <vector>
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 根据先序和中序重建二叉树
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int vinlen = vin.size();
        if(vinlen == 0)
            return nullptr;
        vector<int> pre_left, pre_right, vin_left, vin_right;
        
        //创建根节点，根节点肯定是前序遍历的第一个数
        TreeNode* head = new TreeNode(pre[0]);
        //找到中序遍历根节点所在位置,存放于变量gen中
        int gen = 0;
        for(int i = 0;i < vinlen; i++){
            if(vin[i] == pre[0]){
                gen = i;
                break;
            }
        }
        
        //对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
        // 找出head对应的左子树的所有节点
        for(int i = 0; i < gen; i++){
            vin_left.push_back(vin[i]);
            pre_left.push_back(pre[i + 1]);//先序第一个为根节点
        }
        
        // 找出head对应的右子树的所有节点
        for(int i = gen + 1; i < vinlen; i++){
            vin_right.push_back(vin[i]);
            pre_right.push_back(pre[i]);
        }
        
        //递归，执行上述步骤，区分子树的左、右子子树，直到叶节点
        head->left = reConstructBinaryTree(pre_left, vin_left);
        head->right = reConstructBinaryTree(pre_right, vin_right);
        return head;
    }
};