面试题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++版本：

/**
 * 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 NULL;
        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;
            }
        }
        //对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
        // 左子树
        for(int i = 0; i < gen; i++){
            vin_left.push_back(vin[i]);
            pre_left.push_back(pre[i+1]);//先序第一个为根节点
        }
        // 右子树
        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;
    }
};

面试题7：重建二叉树

原文：https://www.cnblogs.com/flyingrun/p/13281335.html