題目

描述

根據(jù)前序遍歷和中序遍歷樹構(gòu)造二叉樹.

樣例

樣例 1:
    輸入:  in-order = [], pre-order = []
    輸出: null  


樣例 2:
    輸入: in-order = [1,2,3], pre-order = [2,1,3]
    輸出:  
    
      2
     / \
    1   3

注意事項

你可以假設樹中不存在相同數(shù)值的節(jié)點

解答

思路

根據(jù)注意事項，前序遍歷的節(jié)點從根節(jié)點開始，那么在中序遍歷中對應的節(jié)點的左邊就是其左子樹，右邊就是其右子樹了。

代碼

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // write your code here
        if (preorder.length == 0 && inorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int length = inorder.length;
        int rootIndex = 0;
        for (int a : inorder) {
            if (a == preorder[0]) {
                break;
            }
            rootIndex++;
        }
        root.left = buildTree(java.util.Arrays.copyOfRange(preorder, 1, 1 + rootIndex), java.util.Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(java.util.Arrays.copyOfRange(preorder, rootIndex + 1, length), java.util.Arrays.copyOfRange(inorder, rootIndex + 1, length));
        return root;
    }
}