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.

方法

依据树的中序遍历和前序遍历，来构造树。使用递归的思想。

	TreeNode getTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
		if (preStart >= preEnd) {
			return null;
		}
		int cur = preorder[preStart];
		TreeNode root = new TreeNode(cur);
		int i = 0;
		int j = inStart;
		while(inorder[j] != cur) {
			j++;
			i++;
		}
		root.left = getTree(preorder, preStart + 1, preStart + i + 1, inorder, inStart, inStart + i);
		root.right = getTree(preorder, preStart + i + 1, preEnd, inorder, inStart + i + 1, inEnd);
		
		return root;
	}
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	if (preorder == null) {
    		return null;
    	}
    	int len = preorder.length;
    	return getTree(preorder, 0, len, inorder, 0, len);
    }

版权声明：本文博客原创文章，博客，未经同意，不得转载。