LeetCode 105：从前序与中序遍历构造二叉树，Java 递归解法详解

一、题目描述给定一棵二叉树的前序遍历preorder和中序遍历inorder请还原这棵二叉树。题目保证数组中没有重复元素。preorder [3, 9, 20, 15, 7] inorder [9, 3, 15, 20, 7]构造结果如下3 / \ 9 20 / \ 15 7关键是从两种遍历序列中确定根节点并划分左右子树。二、前序找根中序分左右先回顾遍历顺序前序遍历根 - 左 - 右 中序遍历左 - 根 - 右前序遍历的第一个元素3是根节点。在中序遍历中找到3[9, 3, 15, 20, 7] ↑ 根节点根节点左边的[9]属于左子树右边的[15,20,7]属于右子树。左子树只有一个节点因此可以同步划分前序遍历左子树preorder [9]inorder [9] 右子树preorder [20,15,7]inorder [15,20,7]两个子问题与原问题结构相同因此可以递归构造从前序遍历中取出当前根节点在中序遍历中找到根节点的位置递归构造左子树递归构造右子树。三、完整 Java 代码class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int len preorder.length; if (len 0) { return null; } TreeNode root new TreeNode(preorder[0]); // 找到根节点在中序遍历中的索引位置,这个值也是左子树的所有元素个数 int rootInInorder indexOf(inorder, preorder[0]); // 前序遍历中左子树的部分和右子树的部分 int[] preLeft Arrays.copyOfRange(preorder, 1, 1 rootInInorder); // 复制是左闭右开区间 int[] preRight Arrays.copyOfRange(preorder, 1 rootInInorder, len); // 中序遍历中左子树的部分和右子树的部分 int[] inLeft Arrays.copyOfRange(inorder, 0, rootInInorder); int[] inRight Arrays.copyOfRange(inorder, 1 rootInInorder, len); // 递归构建左右子树 root.left buildTree(preLeft, inLeft); root.right buildTree(preRight, inRight); return root; } // 返回 x 在 a 中的下标保证 x 一定在 a 中 private int indexOf(int[] a, int x) { for (int i 0; ; i) { if (a[i] x) { return i; } } } }四、常见错误1. 把中序遍历的第一个元素当成根节点根节点由前序遍历确定中序遍历只负责划分左右区域。2. 先构造右子树全局指针按“根、左、右”移动必须先递归左子树。3. 区间没有排除根节点正确边界为root.left build(inorderLeft, rootIndex - 1); root.right build(rootIndex 1, inorderRight);