网站需要多大宽带,phpstudy2016快速搭建网站,公司怎么做网页,ps上做网站【LetMeFly】105.从前序与中序遍历序列构造二叉树#xff1a;分治#xff08;递归#xff09;——五彩斑斓的题解#xff08;若不是彩色的可以点击原文链接查看#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/construct-binary-tree-from-preorder-a…【LetMeFly】105.从前序与中序遍历序列构造二叉树分治递归——五彩斑斓的题解若不是彩色的可以点击原文链接查看
力扣题目链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
给定两个整数数组 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]提示:
1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列
方法一分治递归
前序遍历根 左子树 右子树中序遍历左子树 根 右子树
写一个函数dfs接收前序遍历数组和中序遍历数组作为参数 根据前序遍历数组的第一个元素为根节点建立节点找到根节点在中序遍历数组中的位置 以此可得到左子树和右子树的长度信息 以此可确定左子树和右子树在两个数组中的位置 递归建立左子树和右子树 递归的终止条件为“前序遍历数组为空”此时返回空节点。
Tips: 可以在预处理时建立一个哈希表以便能快速地找到根节点在中序遍历数组中的位置。
时间复杂度 O ( N ) O(N) O(N)其中 N N N是节点个数空间复杂度 O ( N ) O(N) O(N)
AC代码
C
class Solution {
private:unordered_mapint, vectorint::iterator ma;TreeNode* dfs(vectorint::iterator preLeft, vectorint::iterator preRight, vectorint::iterator inLeft, vectorint::iterator inRight) {if (preRight preLeft) {return nullptr;}TreeNode* thisNode new TreeNode(*preLeft);vectorint::iterator loc ma[*preLeft];int leftLength loc - inLeft;thisNode-left dfs(preLeft 1, preLeft leftLength 1, inLeft, loc);thisNode-right dfs(preLeft leftLength 1, preRight, loc 1, inRight);return thisNode;}public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {for (vectorint::iterator it inorder.begin(); it ! inorder.end(); it) {ma[*it] it;}return dfs(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());}
};Python
from typing import List, Optional# Definition for a binary tree node.
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution: # AC,98.61%,91.88%def dfs(self, preLeft: int, preRight: int, inLeft: int, inRight: int) - Optional[TreeNode]:if preRight preLeft:return NonethisNode TreeNode(self.preorder[preLeft])loc self.ma[self.preorder[preLeft]]leftLength loc - inLeftthisNode.left self.dfs(preLeft 1, preLeft leftLength 1, inLeft, loc - 1)thisNode.right self.dfs(preLeft leftLength 1, preRight, loc 1, inRight)return thisNodedef buildTree(self, preorder: List[int], inorder: List[int]) - TreeNode:self.preorder preorderself.inorder inorderself.ma dict()for i in range(len(inorder)):self.ma[inorder[i]] ireturn self.dfs(0, len(preorder), 0, len(inorder))同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136186356
