首页 > 代码库 > 【leetcode】Construct Binary Tree from Preorder and Inorder Traversal

【leetcode】Construct Binary Tree from Preorder and Inorder Traversal

问题:

给定二叉树的前序和中序遍历,重构这课二叉树.

分析:

前序、中序、后序都是针对于根结点而言,所以又叫作先根、中根、后根(当然不是高跟)。
前序:根  左 右
中序:左  根 右
对二叉树,我们将其进行投影,就会发现个有趣的事:

发现投影后的顺序,恰好是中序遍历的顺序,这也就是为什么在构造二叉树的时候,一定需要知道中序遍历,因为中序遍历决定了结点间的相对左右位置关系。所以,对一串有序的数组,我们可以来构建二叉有序数,并通过中序遍历,就可以得到这个有序的数组。
既然中序遍历可以通过根结点将序列分为左右两个部分,那么,给出连续的根序列(由前序或后序给出),我们就可以对整个序列进行不断的划分,就可以确定左右关系,就能够构建符合这种遍历的唯一的树。

前序的 1 将中序分成两个分, 3将 4 3,5 分成了两部分,2,4,5 分别对应一个,这里就不画了。

总结来说:前序的根将中序分割成左子树和右子树,随着不断的进行,中序的划分也不断的具体,最后构造出整个树。

实现:

  TreeNode* addNode(vector<int> &preorder, int& start1, vector<int>& inorder, int start2, int end2)
{
	if(start1 >= preorder.size() || end2 < start2)
	{
	    //doesn't has left branch
		--start1;
		return NULL;
	}
	//construct the root node
	TreeNode *root = new TreeNode(preorder[start1]);

	int i;//the index of current root in inorder
	for ( i = start2; i <= end2; ++i)
	{
		if(inorder[i] == preorder[start1])
			break;
	}
    //construct left branch
	root->left = addNode(preorder, ++start1, inorder, start2, i - 1);
    // construct right branch
	root->right = addNode(preorder, ++start1, inorder, i + 1, end2);
	
	return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

	if(preorder.size() <= 0)
		return NULL;
	int start = 0;
	
	TreeNode *root = addNode(preorder, start, inorder, 0, inorder.size() - 1);
	return root;
}

也可以在preorder中给定两个参数,表示起始点。
//
 TreeNode *createTree(vector<int>& preorder, int left1, int right1, vector<int>&inorder, int left2, int right2)
    {
        if(right1 < left1 || right2 < left2 )
        return NULL;
        TreeNode *root = new TreeNode(preorder[left1]);
        
        int i = left2;
        for(; i <= right2; ++i){
            if(inorder[i] == preorder[left1])
            break;
        }
        if(i > right2)  return NULL;
        root->left = createTree(preorder, left1 + 1, left1 + i - left2, inorder, left2, i - 1);
        root->right = createTree(preorder, left1 + i - left2 + 1, right1, inorder, i + 1, right2);
        return root;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if(preorder.size() == 0 || inorder.size() == 0 || preorder.size() != inorder.size())
        return NULL;
        TreeNode *root = createTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        return root;
    }


这样的话preorder的起始结点就需要细心。代码直接在leetcode上敲的,有些排版好像不是很规整。