数据结构与算法——Java实现 46. 从前序与中序遍历序列构造二叉树
努力的意义大概就是当好运来临的时候
你觉得你值得
—— 24.10.24
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组
preorder
和inorder
,其中preorder
是二叉树的先序遍历,inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
递归
思路
根据前序遍历结果寻找树的根结点,因为题目中说明所有根节点的值都不会重复,所以可以在中序遍历序列中,根节点左边的则是二叉树的左子树,根节点右边的则是二叉树的右子树
寻找到左子树后进行递归,通过前序遍历寻找出左子树的根,再通过中序遍历中根节点位置的左右寻找左子树的左右节点,右子树同样,通过前序遍历寻找出右子树的根,再通过中序遍历中根节点位置的左右寻找右子树的左右节点
不断进行递归,直到找到全部的叶子节点
代码实现
/*** 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 == null || inorder == null || preorder.length == 0 || inorder.length == 0) {return null;}int rootVal = preorder[0];TreeNode root = new TreeNode(rootVal);// 区分左右子树for (int i = 0; i < inorder.length; i++) {if (inorder[i] == rootVal) {int[] inLeft = Arrays.copyOfRange(inorder, 0, i);int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);int[] preLeft = Arrays.copyOfRange(preorder, i, i + 1);int[] preRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);root.left = buildTree(preLeft, inLeft);root.right = buildTree(preRight, inRight);break;}}return root;}
}
注: Arrays.copyOfRange的三个参数是:被拷贝的数组,拷贝的起始长度,拷贝的终结长度,拷贝数组的长度注意是左闭右开的