支付宝网站开发,广州十大科技公司,机关单位网站安全建设,毕业设计怎么做网站目录
题目#xff1a;剑指 Offer 06. 从尾到头打印链表 - 力扣#xff08;LeetCode#xff09;
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
题目#xff1a;剑指 Offer 07. 重建二叉树 - 力扣#xf…目录
题目剑指 Offer 06. 从尾到头打印链表 - 力扣LeetCode
题目的接口
解题思路
代码
过啦
题目剑指 Offer 07. 重建二叉树 - 力扣LeetCode
题目的接口
解题思路
代码
过啦
写在最后 题目剑指 Offer 06. 从尾到头打印链表 - 力扣LeetCode 题目的接口
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func reversePrint(head *ListNode) []int {}
解题思路
这道题我读完之后想到了两种思路1、直接从后往前去链表的值放进数组但是这样既不好写复杂度也非常的高不推荐
2、先将链表存进一个临时数组再创建一个返回数组将临时数组的值从后往前存进返回数组中这样就实现了来看代码
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/func reversePrint(head *ListNode) []int {r : make([]int, 0)for head ! nil {r append(r, head.Val)head head.Next} ans : make([]int, 0)i : len(r) - 1for i 0 {ans append(ans, r[i])i--}return ans
}
不过做完这道题之后我去翻看题解区看到了一个大佬写了一个很妙的解法就是利用递归的特性用 append 函数将链表的值倒着连接成一个切片返回。
代码
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func reversePrint(head *ListNode) []int {var f func(head *ListNode) []int f func(head *ListNode) []int {if head nil {return []int{}}return append(f(head.Next), head.Val) }return f(head)
}
过啦 题目剑指 Offer 07. 重建二叉树 - 力扣LeetCode 题目的接口
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func buildTree(preorder []int, inorder []int) *TreeNode {}
解题思路
这种二叉树的题目一般也是有两种解法一个递归一个迭代递归比较简单所以我们当然是先来递归这里递归的核心思路就是根据题目给的前序和中序遍历找到这棵树的根节点以及左右子树具体思路如下
前序的第一个值就是根节点根据这个根节点我们就能找到中序遍历中的根节点位置然后将中序数组分成左右子树两个部分再根据中序左右子树的长度我们就能找到前序数组左右字数的位置再递归求解即可代码如下
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func buildTree(preorder []int, inorder []int) *TreeNode {for k : range inorder {if inorder[k] preorder[0] {return TreeNode {Val: preorder[0],Left: buildTree(preorder[1:k1], inorder[0:k]),Right: buildTree(preorder[k1:], inorder[k1:]),} }}return nil
}
递归求解还是相对简单的比较有难度的就是迭代的解法使用这个迭代法的核心思想就是若这颗树是一颗只有左子树的树,相当于一条单链表 那中序遍历和先序遍历的结果是反过来的利用这个特性我们就能用栈来存储节点到最左下的位置时开始取栈中元素和中序数组匹配如果遇到不相等的情况证明这个不相等的值是右节点代码思路如下
代码
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func buildTree(preorder []int, inorder []int) *TreeNode {if len(preorder) 0 {return nil}root : TreeNode{preorder[0], nil, nil}stack : []*TreeNode{}stack append(stack, root)var inorderIndex int// 首先一直遍历到最左下的地方// 这里的意思就是一直找左子树直到找不到for i : 1; i len(preorder); i {preorderVal : preorder[i]node : stack[len(stack)-1]if node.Val ! inorder[inorderIndex] {node.Left TreeNode{preorderVal, nil, nil} // 组装二叉树的左子树stack append(stack, node.Left)} else { // 已经到了最左下的位置// 这里的逻辑是不断出栈直到不匹配而不匹配的那个节点就是右节点for len(stack) ! 0 stack[len(stack)-1].Val inorder[inorderIndex] {node stack[len(stack)-1]stack stack[:len(stack)-1]inorderIndex}// 将这个右子树的节点入栈// 也就是这个右子树将作为新的根节点继续找他的左子树(重新上去走循环)node.Right TreeNode{preorderVal, nil, nil} // 组装二叉树的右子树stack append(stack, node.Right)}}return root
}
过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
