`
huntfor
  • 浏览: 194215 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Construct Binary Tree from Preorder and Inorder Traversal

 
阅读更多

新博文地址:

[leetcode]Construct Binary Tree from Preorder and Inorder Traversal

 

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.

 根据前序遍历和中序遍历构建二叉树,构建二叉树必须要有中序遍历,前序和后序可选其一。如果对建树过程不太熟悉的朋友,可以看这里。里面很详细的讲解了二叉树的重构过程。算法肯定是一样的,就不多说了,大家可以看这里,代码如下:

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    	if(preorder.length <= 0){
    		return null;
    	}
        if(preorder.length == 1){
        	return new TreeNode(preorder[0]);
        }
    	
    	TreeNode root = new TreeNode(preorder[0]);
    	int[] leftInorder = getSubArray(inorder, root.val);
    	int[] rightInorder = Arrays.copyOfRange(inorder, leftInorder.length + 1, inorder.length);
    	int[] leftPreOrder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
    	int[] rightPreOrder = Arrays.copyOfRange(preorder, leftPreOrder.length + 1, preorder.length);
    	root.left = buildTree(leftPreOrder, leftInorder);
    	root.right = buildTree(rightPreOrder, rightInorder);
    	return root;
    }
    
    private int[] getSubArray(int[] inorder,int rootVal){
    	int length = 0;
    	for(length = 0; length < inorder.length; length++){
    		if(inorder[length] == rootVal){
    			break;
    		}
    	}
    	return Arrays.copyOf(inorder, length);
    }

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics