称号

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);    }

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