哪个网站的图片可以做素材,广告推广是什么工作,哈尔滨工程建设网,陵水网站建设介绍剑指 Offer 07. 重建二叉树、16. 数值的整数次方、33. 二叉搜索树的后序遍历序列
题目描述#xff1a; [07] 输入某二叉树的前序遍历和中序遍历的结果#xff0c;请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 [16] 实现 pow(x,…剑指 Offer 07. 重建二叉树、16. 数值的整数次方、33. 二叉搜索树的后序遍历序列
题目描述 [07] 输入某二叉树的前序遍历和中序遍历的结果请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 [16] 实现 pow(x, n) 即计算 x 的 n 次幂函数即xn。不得使用库函数同时不需要考虑大数问题。 [33] 输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true否则返回 false。假设输入的数组的任意两个数字都互不相同。
考察重点 第07题先通过先序数组确定中间节点A再进入中序数组找到A将中序数组划分为左右两部分即左右子树依次递归。 第16题以2的倍数累加乘积即每次以tt1,2,4…;nowN1248…个x相乘当nowN tt n时n-nowNnowN置0tt置1重新开始累加。 第33题后序遍历数组中间节点在数组末尾由于是二叉搜索树因此每次只需从首位开始查找连续的小于末尾元素的子数组作为左子树查找连续的大于末尾元素的子数组作为右子树。如果左右子树元素之和刚好等于当前数组-1即左右子树元素之和根节点当前数组元素之和说明当前数组符合条件继续遍历左右子树。
第07题
func dfs(preorder []int, inorder []int)*TreeNode {i : 0for ;i len(inorder);i {if preorder[0] inorder[i]{break}}root : TreeNode{Val: preorder[0], Left:nil, Right:nil}leftLen : len(inorder[0:i])rightLen : len(inorder[i1:])if leftLen 0{root.Left nil}else{root.Left dfs(preorder[1:leftLen1], inorder[0:i])}if rightLen 0{root.Right nil}else{root.Right dfs(preorder[leftLen1:], inorder[i1:])}return root
}
func buildTree(preorder []int, inorder []int) *TreeNode {if len(preorder) 0 || len(inorder) 0{return nil}return dfs(preorder, inorder)
}第16题
func myPow(x float64, n int) float64 {res : 1.0mark : trueif n 0{mark falsen -n}for n ! 0{nowN : 0tt : 1nowX : xfor nowN - tt n{res res * nowXnowX * nowXnowN - tttt * 2}n - nowN}if mark{res 1 / res}return res
}第33题
func dfs(postorder []int)bool{ point : 0oLen : len(postorder) - 1if oLen -1{return true}for ;point oLen postorder[point] postorder[oLen];point {}recLeft : point for ;point oLen postorder[point] postorder[oLen];point {}return point oLen dfs(postorder[0:recLeft]) dfs(postorder[recLeft:oLen])
}func verifyPostorder(postorder []int) bool {return dfs(postorder);
}
