从前序与中序遍历序列构造二叉树
# 📃 题目描述
题目链接:
- 剑指 Offer 07. 重建二叉树 (opens new window)
- 105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-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) {
// 左闭右开
return buildTree1(preorder, 0, preorder.length,
inorder, 0, inorder.length);
}
/**
* @param preorder (左闭右开)
* @param preLeft preorder 数组的起始下标
* @param preRight preorder 数组的终止下标
* @param inorder (左闭右开)
* @param inLeft inorder 数组的起始下标
* @param inRight inorder 数组的终止下标
* @return
*/
private TreeNode buildTree1(int[] preorder, int preLeft, int preRight,
int[] inorder, int inLeft, int inRight) {
// 没有元素了
if (inRight - inLeft < 1) {
return null;
}
// 只有一个元素了
if (inRight - inLeft == 1) {
return new TreeNode(inorder[inLeft]);
}
// 前序数组的第一个节点为根节点
TreeNode root = new TreeNode(preorder[preLeft]);
// 在中序数组中找到根节点的位置
int index = inLeft;
for (; index < inRight; index ++) {
if (inorder[index] == root.val) {
break;
}
}
// 构建左子树
root.left = buildTree1(preorder, preLeft + 1, preLeft + 1 + (index - inLeft),
inorder, inLeft, index);
// 构建右子树
root.right = buildTree1(preorder, preLeft + 1 + (index - inLeft) , preRight,
inorder, index + 1, inRight);
return root;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10