leetcode construct-binary-tree-from-preorder-and-inorder-traversal(Java)

leetcode題目

construct-binary-tree-from-preorder-and-inorder-traversal -- newcoder 44
從前序與中序周遊序列構造二叉樹 -- leetcode 105
           

題目描述

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 = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]

    3
   / \
  9  20
    /  \
   15   7
           

思路

* 1、前序周遊序列中的第一個元素為根節點
 * 2、找到該根節點在中序周遊序列中的位置，左側即為
 *    左樹的周遊序列，右側為右樹的周遊序列
 * 3、根據左樹周遊序列的數組長度len，找出前序周遊
 * 	  序列的第2到第len+1個元素，第一個元素即為左樹中的根節點，
 *    右樹的根節點是前序周遊序列的最後一個節點
 * 4、遞歸進行上述過程，建構樹
           

代碼

package com.leetcode.tree;

/**
 * 題目： 
 * construct-binary-tree-from-preorder-and-inorder-traversal -- newcoder 44
 * 從前序與中序周遊序列構造二叉樹 -- leetcode 105
 * 
 * 題目描述：
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 = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]

傳回如下的二叉樹：

    3
   / \
  9  20
    /  \
   15   7
 * 
 */
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {

	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}	
	
	
	/**
	 * 思路： 
	 * 1、前序周遊序列中的第一個元素為根節點
	 * 2、找到該根節點在中序周遊序列中的位置，左側即為
	 *    左樹的周遊序列，右側為右樹的周遊序列
	 * 3、根據左樹周遊序列的數組長度len，找出前序周遊
	 * 	     序列的第2到第len+1個元素，第一個元素即為左樹中的根節點，
	 *    右樹的根節點是前序周遊序列的最後一個節點
	 * 4、遞歸進行上述過程，建構樹
	 */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
        	// empty param
        	return null;
        }
        
        int preLen = preorder.length;
        int inLen = inorder.length;
        
        if (preLen != inLen) {
        	// inValid param
        	return null;
        }
        
        // 隻有一個元素
        if (preLen == 1) {
        	return new TreeNode(preorder[0]);
        }
        
    	return buildTree(preorder, 0, preLen-1, inorder, 0, inLen-1);
    }
    
    private TreeNode buildTree(int[] preOrder, int preBegin, int preEnd, 
    							int[] inOrder, int inBegin, int inEnd) {
    	if (preBegin > preEnd || inBegin > inEnd) {
    		return null;
    	}
    	
    	// 1、根節點的值
    	int rootVal = preOrder[preBegin];
    	
    	// 2、找到該值在中序序列中的索引    	
    	int rootIdxInOrder = -1;
    	for (int i=inBegin; i<= inEnd; i++) {
    		if (inOrder[i] == rootVal) {
    			rootIdxInOrder = i;
    			break;
    		}
    	}
    	// 沒找到，參數不合法，傳回null
    	if (rootIdxInOrder < 0) {
    		return null;
    	}

    	// 3、生成頭節點
    	TreeNode root = new TreeNode(rootVal);
    	
    	// 隻有一個元素，直接傳回，減少遞歸層次
    	if (preBegin == preEnd && inBegin == inEnd) {
    		return root; 
    	}
    	
    	// 4、左子樹長度
    	int leftTreeLen = rootIdxInOrder - inBegin;
    	
    	// 5、前序周遊序列中，左子樹周遊序列結束索引為preBegin + 1 + leftTreeLen - 1
    	int preIdxLeftTreeEnd = preBegin + leftTreeLen;
    	
    	// 6、遞歸處理左右子樹，挂接左右節點， 要去掉目前根節點的索引
    	root.left = buildTree(preOrder, preBegin+1, preIdxLeftTreeEnd, 
    							inOrder, inBegin, rootIdxInOrder-1);
    	root.right = buildTree(preOrder, preIdxLeftTreeEnd+1, preEnd, 
    							inOrder, rootIdxInOrder+1, inEnd);
    	
    	return root;
    } 
    
	public static void main(String[] args) {
		int[] preOrder = {3,9,20,15,7};
		int[] inOrder = {9,3,15,20,7};
		System.out.println(new ConstructBinaryTreeFromPreorderAndInorderTraversal().buildTree(preOrder,inOrder).val);
	}

}