做外单都有什么网站,建个网站做网络推广要花多少钱,做网贷中介网站赚钱吗,营销型网站制作多少钱前言
今天的五道题都是层序遍历的模板#xff0c;深度优先的递归还不太熟。继续努力。
内容
一、在每个树行中找最大值
515.在每个树行中找最大值
给定一棵二叉树的根节点 root #xff0c;请找出该二叉树中每一层的最大值。
广度优先搜素
时间复杂度#xff1a;O(n)…前言
今天的五道题都是层序遍历的模板深度优先的递归还不太熟。继续努力。
内容
一、在每个树行中找最大值
515.在每个树行中找最大值
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
广度优先搜素
时间复杂度O(n)其中 nnn 为二叉树节点个数每一个节点仅会进出队列一次。
空间复杂度O(n)存储二叉树节点的空间开销。
func largestValues(root *TreeNode) []int {var res []intif rootnil{return res}//没有这个会panic: runtime error: invalid memory address or nil pointer dereference curLevel:[]*TreeNode{root}for len(curLevel)0{nextLevel:[]*TreeNode{}maxVal:math.MinInt32for _,node:range curLevel{maxVal Max(maxVal,node.Val)if node.Left!nil{nextLevelappend(nextLevel,node.Left)}if node.Right!nil{nextLevelappend(nextLevel,node.Right)}}resappend(res,maxVal)curLevelnextLevel}return res
}func Max(a,b int)int{if ab{return a}else{return b}
}
深度优先搜索
时间复杂度O(n)其中 nnn 为二叉树节点个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度O(height)。其中 height 表示二叉树的高度。递归函数需要栈空间而栈空间取决于递归的深度因此空间复杂度等价于二叉树的高度。
func largestValues(root *TreeNode)(ans []int){var dfs func(*TreeNode,int)dfsfunc(node *TreeNode,height int){if nodenil{return}if heightlen(ans){ansappend(ans,node.Val)}else{ans[height]max(ans[height],node.Val)}dfs(node.Left,height1)dfs(node.Right,height1)}dfs(root,0)return
}
func max(a,b int)int{if ab{return a}else{return b}
}
二、填充每个节点的下一个右侧节点指针
116.填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。
广度优先搜素
/*** Definition for a Node.* type Node struct {* Val int* Left *Node* Right *Node* Next *Node* }*/func connect(root *Node) *Node {if rootnil{return root}curLevel:[]*Node{root}for len(curLevel)0{temp:curLevelcurLevelnilfor i,node:range temp{if i1len(temp){node.Nexttemp[i1]}if node.Left!nil{curLevelappend(curLevel,node.Left)}if node.Right!nil{curLevelappend(curLevel,node.Right)}}}return root
}
使用已建立的next 指针
时间复杂度O(N)每个节点只访问一次。
空间复杂度O(1)不需要存储额外的节点。
func connect(root *Node)*Node{if rootnil{return root}// 每次循环从该层的最左侧节点开始for leftmost:root;leftmost.Left!nil;leftmostleftmost.Left{// 通过 Next 遍历这一层节点为下一层的节点更新 Next 指针for node:leftmost;node!nil;nodenode.Next{// 左节点指向右节点node.Left.Nextnode.Rightif node.Next!nil{// 右节点指向下一个左节点node.Right.Nextnode.Next.Left}}}return root
}
三、填充每个节点的下一个右侧节点指针II
117.填充每个节点的下一个右侧节点指针II
给定一个二叉树
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL 。
初始状态下所有 next 指针都被设置为 NULL 。
广度优先搜素
一模一样的代码 注意curLevel和temp 不要写混了
func connect(root *Node) *Node {if rootnil{return root}curLevel:[]*Node{root}for len(curLevel)0{temp:curLevelcurLevelnilfor i,node:range temp{if i1len(temp){node.Nexttemp[i1]}if node.Left!nil{curLevelappend(curLevel,node.Left)}if node.Right!nil{curLevelappend(curLevel,node.Right)}}}return root
}
四、二叉树的最大深度
104.二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
广度优先搜素
func maxDepth(root *TreeNode) int {var ans intif rootnil{return ans}curLevel:[]*TreeNode{root}for len(curLevel)0{temp:curLevelcurLevelnilfor _,node:range temp{if node.Left!nil{ curLevelappend(curLevel,node.Left)}if node.Right!nil{curLevelappend(curLevel,node.Right)}}ans//记录深度其他的是层序遍历的板子}return ans
}
深度优先搜索
func maxDepth(root *TreeNode)int{if rootnil{return 0}return max(maxDepth(root.Left),maxDepth(root.Right))1
}
func max(a,b int)int{if ab{return a}return b
}
五、二叉树的最小深度
111.二叉树的最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
广度优先搜素
func minDepth(root *TreeNode) int {var ans intif rootnil{return ans}curLevel:[]*TreeNode{root}for len(curLevel)0{temp:curLevelcurLevelnilfor _,node:range temp{if node.Leftnilnode.Rightnil{return ans1}if node.Left!nil{ curLevelappend(curLevel,node.Left)}if node.Right!nil{curLevelappend(curLevel,node.Right)}}ans}return ans
}
深度优先搜索
func minDepth(root *TreeNode)int{if rootnil{return 0}if root.Leftnilroot.Rightnil{return 1}minD:math.MaxInt32if root.Left!nil{minDmin(minD,minDepth(root.Left))}if root.Right!nil{minDmin(minD,minDepth(root.Right))}return minD1
}func min(a,b int)int{if ab{return a}return b
}
最后
即使感知自己身体的需求不管是体力消耗还是脑力消耗及时补充能量吃饭休息。
