题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
package com.hhdd.数据结构.树;
/**
* @Author huanghedidi
* @Date 2022/8/23 22:44
*/
public class 重建二叉树 {
/**
* 根据前序遍历和中序遍历重建一棵二叉树
*
* @param pre
* @param vin
* @return
*/
public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
if (pre.length == 0 || vin.length == 0){
return null;
}
return rebuild(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
}
public TreeNode rebuild(int[] pre, int preStart, int preEnd, int[] vin, int vinStart, int vinEnd) {
TreeNode root = new TreeNode(pre[preStart]);
// 在中序遍历中可以找到前序遍历的节点，节点位置往前是左子树，节点位置往后是右子树
int midIndex = vinStart;
for (int i = vinStart; i <= vinEnd; i++) {
if (vin[i] == pre[preStart]) {
midIndex = i;
}
}
int leftLength = midIndex - vinStart;
int rightLength = vinEnd - midIndex;
// 判断是否有左右子树
if (leftLength > 0) {
root.left = rebuild(pre, preStart + 1, preStart + leftLength, vin, vinStart, midIndex - 1);
}
if (rightLength > 0) {
root.right = rebuild(pre, preStart + leftLength + 1, preEnd, vin, midIndex + 1, vinEnd);
}
return root;
}
}
