【二叉树专题】—— 反向构造二叉树

LeetCode 105: 从前序与中序遍历序列构造二叉树

📖 解题思路：

（1）首先要明确两种遍历的形式：

前序遍历：也称为先根遍历，根结点 左孩子 右孩子
中序遍历：左孩子 根结点 右孩子

也就是说：通过前序遍历我们可以判断根结点，结合中序遍历我们可以判断出当前结点的左右子树。

（2）我选择创建四个数组，来不断维护前序、中序遍历的左右子树

（3）如果数组长度为零，那么直接返回空即可，也是递归的结束条件

PS: 数组长度为零与数组初始化为空有什么区别？

数组为空，代表数组的引用没有指向为数组堆中的空间，Java虚拟机没有在堆中为数组分配空间
数组长度为零，代表Java虚拟机为数组分配了空间，也有将数组的引用指向Java虚拟机在堆中分配的内存

（4）创建好根结点后，遍历数组（两个数组的长度是相同的），找到当前根结点在中序遍历中的索引，然后创建前序遍历和中序遍历的左右子树保存数组，然后再根据四个数组递归来构建左右子树

📝 Java代码部分:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *  this.val = val; *  this.left = left; *  this.right = right; *     } * } */class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { /**     前序遍历确定根结点，中序遍历确定左右子树  */ if(preorder.length == 0 || inorder.length == 0){     return null; } //创建根结点 TreeNode root = new TreeNode(preorder[0]); //遍历inorder数组 for(int i = 0; i < preorder.length; i++){     //找到当前根结点在inorder数组中的索引     if(preorder[0] == inorder[i]){  //创建当前结点中序遍历左右子树的数组  int [] inorder_left = Arrays.copyOfRange(inorder, 0, i);  int [] inorder_right = Arrays.copyOfRange(inorder, i + 1, inorder.length);  //创建当前结点前序遍历左右子树的数组  int [] preorder_left = Arrays.copyOfRange(preorder, 1, i + 1);  int [] preorder_right = Arrays.copyOfRange(preorder, i + 1, preorder.length);  //递归创建左右子树  root.left = buildTree(preorder_left, inorder_left);  root.right = buildTree(preorder_right, inorder_right);  // break;     } } return root;    }}

LeetCode 106: 从中序和后序遍历序列构造二叉树

⭕️ 解题思路：
（1）与上边的属于同类型问题，解决此题的重点在于找到左右子树的结点个数，这样在创建中序和后续遍历的左右子树数组时才不会出现问题

（2）补充说明：

Arrays.copyOfRangr(int [] arr, index1, index2)
是Java中完成数组拷贝的方法，返回的是 arr数组索引从 index1 - (index2 - 1)的子数组

❌ Java代码部分：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *  this.val = val; *  this.left = left; *  this.right = right; *     } * } */class Solution {    public TreeNode buildTree(int[] inorder, int[] postorder) { if(inorder.length == 0 || postorder.length == 0){     return null; } //创建根结点 TreeNode root = new TreeNode(postorder[postorder.length - 1]); //遍历中序序列 for(int i = 0; i < inorder.length; i++){     //找到当前根结点在中序遍历中的索引     if(postorder[postorder.length - 1] == inorder[i]){  //创建中序遍历和后序遍历的左右子树  int [] inorder_left = Arrays.copyOfRange(inorder, 0, i);  int [] inorder_right = Arrays.copyOfRange(inorder, i + 1, inorder.length);  int [] postorder_left = Arrays.copyOfRange(postorder, 0, i);  int [] postorder_right = Arrays.copyOfRange(postorder, i, postorder.length - 1);  //创建左右子树  root.left = buildTree(inorder_left, postorder_left);  root.right = buildTree(inorder_right, postorder_right);     } } //返回根结点 return root;    }}

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖茶叶商城