Leetcode 105 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal) 题解分析

题目介绍

Given preorder and inorder traversal of a tree, construct the binary tree.
给定一棵树的前序和中序遍历,构造出一棵二叉树

注意

You may assume that duplicates do not exist in the tree.
你可以假设树中没有重复的元素。(PS: 不然就没法做了呀)

例子:

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

返回的二叉树

  3
 / \
9  20
  /  \
 15   7

简要分析

看到这个题可以想到一个比较常规的解法就是递归拆树,前序就是根左右,中序就是左根右,然后就是通过前序已经确定的根在中序中找到,然后去划分左右子树,这个例子里是 3,找到中序中的位置,那么就可以确定,9 是左子树,15,20,7是右子树,然后对应的可以根据左右子树的元素数量在前序中划分左右子树,再继续递归就行

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
      // 获取下数组长度
        int n = preorder.length;
        // 排除一下异常和边界
        if (n != inorder.length) {
            return null;
        }
        if (n == 0) {
            return null;
        }
        if (n == 1) {
            return new TreeNode(preorder[0]);
        }
        // 获得根节点
        TreeNode node = new TreeNode(preorder[0]);
        int pos = 0;
        // 找到中序中的位置
        for (int i = 0; i < inorder.length; i++) {
            if (node.val == inorder[i]) {
                pos = i;
                break;
            }
        }
        // 划分左右再进行递归,注意下`Arrays.copyOfRange`的用法
        node.left = buildTree(Arrays.copyOfRange(preorder, 1, pos + 1), Arrays.copyOfRange(inorder, 0, pos));
        node.right = buildTree(Arrays.copyOfRange(preorder, pos + 1, n), Arrays.copyOfRange(inorder, pos + 1, n));
        return node;
    }
}