Java for LeetCode 105 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.

解题思路一：

preorder[0]为root，以此分别划分出inorderLeft、preorderLeft、inorderRight、preorderRight四个数组，然后root.left=buildTree(preorderLeft,inorderLeft); root.right=buildTree(preorderRight,inorderRight)

JAVA实现如下：

	public TreeNode buildTree(int[] preorder, int[] inorder) {

		if (preorder.length == 0 || preorder.length != inorder.length)

			return null;

		TreeNode root = new TreeNode(preorder[0]);

		int index = 0;

		for (int i = 0; i < inorder.length; i++)

			if (inorder[i] == root.val) {

				index = 0;

				break;

			}

		int[] inorderLeft = new int[index], preorderLeft = new int[index];

		int[] inorderRight = new int[inorder.length - 1 - index], preorderRight = new int[inorder.length

				- 1 - index];

		Set<Integer> inorderLeftSet=new HashSet<Integer>();

		for (int i = 0; i < inorderLeft.length; i++){

			inorderLeft[i] = inorder[i];

			inorderLeftSet.add(inorder[i]);

		}

		for (int i = 0; i < inorderRight.length; i++)

			inorderRight[i] = inorder[index + i + 1];

		int j = 0, k = 0;

		for (int i = 0; i < preorder.length; i++) {

			if(inorderLeftSet.contains(preorder[i]))

				preorderLeft[j++]=preorder[i];

			else if(preorder[i]!=root.val)

				preorderRight[k++]=preorder[i];

		}

		if(buildTree(preorderLeft,inorderLeft)!=null)

		    root.left=buildTree(preorderLeft,inorderLeft);

		if(buildTree(preorderRight,inorderRight)!=null)

		    root.right=buildTree(preorderRight,inorderRight);

		return root;

	}

结果：Time Limit Exceeded

解题思路二：出现上次解法的原因是因为本人把前序遍历理解成了层次遍历，其实本题是《编程之美》3.9节重建二叉树的原题，书中已经给出的答案，JAVA实现如下：

	static public TreeNode buildTree(int[] preorder, int[] inorder) {

		 return buildTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);

    }

    static public TreeNode buildTree(int[] preorder, int[] inorder, int pBegin, int pEnd, int iBegin, int iEnd){

        if(pBegin>pEnd)

            return null;

        TreeNode root = new TreeNode(preorder[pBegin]);

        int i = iBegin;

        for(;i<iEnd;i++)

            if(inorder[i]==root.val)

                break;

        int lenLeft = i-iBegin;

        root.left = buildTree(preorder, inorder, pBegin+1, pBegin+lenLeft, iBegin, i-1);

        root.right = buildTree(preorder, inorder, pBegin+lenLeft+1, pEnd, i+1, iEnd);

        return root;

    }

巴特西

Java for LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

最新文章

热门文章