🌗 剑指 Offer 07. 重建二叉树
2022年10月10日
- algorithm
🌗 剑指 Offer 07. 重建二叉树
难度: 🌗
问题描述
解法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 思路:
int len = preorder.length;
return mySol(preorder, inorder, 0, len - 1, 0, len - 1);
}
private TreeNode mySol(int[] preorder, int[] inorder, int pl, int pr, int inl, int inr) {
// 递归终止条件
if(pl > pr) {
return null;
}
// pl < pr
int val = preorder[pl];
TreeNode node = new TreeNode(val);
// 在中序数组中找到根节点下标
int index = inl;
while(index <= inr) {
if(inorder[index] == val) {
break;
} else {
index ++;
}
}
node.left = mySol(preorder, inorder, pl + 1, index - inl + pl, inl, index - 1);
node.right = mySol(preorder, inorder, index - inl + pl + 1, pr, index + 1, inr);
return node;
}
}