现在的位置: 首页 > 综合 > 正文

Construct Binary Tree from Preorder and Inorder Traversal (给出前序中序求二叉树)

2014年09月05日 ⁄ 综合 ⁄ 共 1028字 ⁄ 字号 评论关闭

题目原型:

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

Note:

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

基本思路:

根据前序确定根,然后将中序根据根节点切分成两半,如此递归即可。

	public TreeNode buildTree(int[] preorder, int[] inorder)
	{
		if(preorder.length==0&&inorder.length==0)
		{
			return null;
		}
		else
		{
			TreeNode root = new TreeNode(preorder[0]);
			int targetIndex = -1;
			//在中序序列中找到先序序列的第一个节点值,就是根节点值
			for(int i = 0;i<inorder.length;i++)
			{
				if(inorder[i]==preorder[0])
				{
					targetIndex = i;
					break;
				}
			}
			int lenOfLeft = targetIndex;
			int lenOfRight = inorder.length-targetIndex-1;
			
			//找到左子树
			int[] leftPreorder = new int[lenOfLeft];
			int[] leftInorder = new int[lenOfLeft];
			int index = 0;
			while(index<lenOfLeft)
			{
				//赋值左子树
				leftPreorder[index] = preorder[index+1];
				leftInorder[index] = inorder[index];
				index ++;
			}
			root.left = buildTree(leftPreorder, leftInorder);
			
			//找到右子树
			int[] rightPreorder = new int[lenOfRight];
			int[] rightInorder = new int[lenOfRight];
			index = targetIndex+1;
			int i = 0;
			while(i+index<inorder.length)
			{
				//赋值右子树
				rightPreorder[i] = preorder[i+index];
				rightInorder[i] = inorder[i+index];
				i++;
			}
			root.right = buildTree(rightPreorder, rightInorder);
			return root;
		}
	}

抱歉!评论已关闭.