题目描述

根据前序和中序遍历重建二叉树(Java版本)

思路是参考卡子哥的:P

/**
 * Definition for a binary tree node.
 * 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 || inorder.length == 0) return null;
        //调用方法并返回
        return buildHelp(preorder, inorder, 0, preorder.length, 0, inorder.length);
    }

    private TreeNode buildHelp(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        //若前序集合长度为0 返回空
        if(preStart == preEnd) return null;

        //获取根节点
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        //找到中序切割点
        int index;
        for(index = inStart; index < inEnd; index++) {
            if(inorder[index] == rootVal) break;
        }

        //切割中序集合
        int leftInStart = inStart;
        int leftInEnd = index; 
        int rightInStart = index + 1;
        int rightInEnd = inEnd;

        //切割前序集合
        int leftPreStart = preStart + 1;
        int leftPreEnd = leftPreStart + (index - inStart);
        int rightPreStart = leftPreEnd;
        int rightPreEnd = preEnd;

        //遍历左右子树
        root.left = buildHelp(preorder, inorder, leftPreStart, leftPreEnd, leftInStart, leftInEnd);
        root.right = buildHelp(preorder, inorder, rightPreStart, rightPreEnd, rightInStart, rightInEnd);

        return root;
    }
}