Leetcode-105

本来不想发的，但实在没什么可发了。

题目

代码

package eternal.fire;

import java.io.IOException;

public class LeetCode {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        TreeNode root = solution.buildTree(preorder, inorder);
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }

        //根节点
        TreeNode root = new TreeNode(preorder[0]);

        int[] left1, left2, right1, right2;

        //左子树为空
        if (preorder[0] == inorder[0]) {
            left1 = new int[0];
            left2 = new int[0];
        } else {
            //左子树的中序遍历结果
            int index1 = 0;
            for (int i = 0; i < inorder.length; i++) {
                if (inorder[i] == preorder[0]) {
                    index1 = i;
                    break;
                }
            }
            left2 = new int[index1];
            System.arraycopy(inorder, 0, left2, 0, index1);

            //左子树的前序遍历结果
            left1 = new int[index1];
            System.arraycopy(preorder, 1, left1, 0, index1);
        }

        //右子树为空
        if (left1.length + 1 == preorder.length) {
            right1 = new int[0];
            right2 = new int[0];
        } else {
            //右子树的中序遍历结果
            int index2 = 1 + left1.length;
            right2 = new int[preorder.length - 1 - left1.length];
            System.arraycopy(inorder, index2, right2, 0, preorder.length - 1 - left1.length);

            //右子树的先序遍历结果
            right1 = new int[right2.length];
            System.arraycopy(preorder, index2, right1, 0, preorder.length - 1 - left1.length);
        }

        //递归构造左子树
        root.left = buildTree(left1, left2);

        //递归构造右子树
        root.right = buildTree(right1, right2);

        return root;
    }
}

结果