前言
今天的五道題都是層序遍歷的模板，深度優先的遞歸還不太熟。繼續努力。
內容
一、在每個樹行中找最大值
515.在每個樹行中找最大值
給定一棵二叉樹的根節點?root?，請找出該二叉樹中每一層的最大值。
廣度優先搜素
時間復雜度：O(n)，其中 nnn 為二叉樹節點個數，每一個節點僅會進出隊列一次。
空間復雜度：O(n)，存儲二叉樹節點的空間開銷。
func largestValues(root *TreeNode) []int {var res []intif root==nil{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{nextLevel=append(nextLevel,node.Left)}if node.Right!=nil{nextLevel=append(nextLevel,node.Right)}}res=append(res,maxVal)curLevel=nextLevel}return res
}func Max(a,b int)int{if a>b{return a}else{return b}
}深度優先搜索
時間復雜度：O(n)，其中 nnn 為二叉樹節點個數。二叉樹的遍歷中每個節點會被訪問一次且只會被訪問一次。
空間復雜度：O(height)。其中 height 表示二叉樹的高度。遞歸函數需要棧空間，而棧空間取決于遞歸的深度，因此空間復雜度等價于二叉樹的高度。
func largestValues(root *TreeNode)(ans []int){var dfs func(*TreeNode,int)dfs=func(node *TreeNode,height int){if node==nil{return}if height==len(ans){ans=append(ans,node.Val)}else{ans[height]=max(ans[height],node.Val)}dfs(node.Left,height+1)dfs(node.Right,height+1)}dfs(root,0)return
}
func max(a,b int)int{if a>b{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 root==nil{return root}curLevel:=[]*Node{root}for len(curLevel)>0{temp:=curLevelcurLevel=nilfor i,node:=range temp{if i+1<len(temp){node.Next=temp[i+1]}if node.Left!=nil{curLevel=append(curLevel,node.Left)}if node.Right!=nil{curLevel=append(curLevel,node.Right)}}}return root
}使用已建立的next 指針?
時間復雜度：O(N)，每個節點只訪問一次。
空間復雜度：O(1)，不需要存儲額外的節點。
func connect(root *Node)*Node{if root==nil{return root}// 每次循環從該層的最左側節點開始for leftmost:=root;leftmost.Left!=nil;leftmost=leftmost.Left{// 通過 Next 遍歷這一層節點，為下一層的節點更新 Next 指針for node:=leftmost;node!=nil;node=node.Next{// 左節點指向右節點node.Left.Next=node.Rightif node.Next!=nil{// 右節點指向下一個左節點node.Right.Next=node.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 root==nil{return root}curLevel:=[]*Node{root}for len(curLevel)>0{temp:=curLevelcurLevel=nilfor i,node:=range temp{if i+1<len(temp){node.Next=temp[i+1]}if node.Left!=nil{curLevel=append(curLevel,node.Left)}if node.Right!=nil{curLevel=append(curLevel,node.Right)}}}return root
}四、二叉樹的最大深度
104.二叉樹的最大深度
給定一個二叉樹?root?，返回其最大深度。
二叉樹的?最大深度?是指從根節點到最遠葉子節點的最長路徑上的節點數。
廣度優先搜素
func maxDepth(root *TreeNode) int {var ans intif root==nil{return ans}curLevel:=[]*TreeNode{root}for len(curLevel)>0{temp:=curLevelcurLevel=nilfor _,node:=range temp{if node.Left!=nil{ curLevel=append(curLevel,node.Left)}if node.Right!=nil{curLevel=append(curLevel,node.Right)}}ans++//記錄深度，其他的是層序遍歷的板子}return ans
}深度優先搜索
func maxDepth(root *TreeNode)int{if root==nil{return 0}return max(maxDepth(root.Left),maxDepth(root.Right))+1
}
func max(a,b int)int{if a>b{return a}return b
}五、二叉樹的最小深度
111.二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
說明：葉子節點是指沒有子節點的節點。
廣度優先搜素
func minDepth(root *TreeNode) int {var ans intif root==nil{return ans}curLevel:=[]*TreeNode{root}for len(curLevel)>0{temp:=curLevelcurLevel=nilfor _,node:=range temp{if node.Left==nil&&node.Right==nil{return ans+1}if node.Left!=nil{ curLevel=append(curLevel,node.Left)}if node.Right!=nil{curLevel=append(curLevel,node.Right)}}ans++}return ans
}深度優先搜索
func minDepth(root *TreeNode)int{if root==nil{return 0}if root.Left==nil&&root.Right==nil{return 1}minD:=math.MaxInt32if root.Left!=nil{minD=min(minD,minDepth(root.Left))}if root.Right!=nil{minD=min(minD,minDepth(root.Right))}return minD+1
}func min(a,b int)int{if a<b{return a}return b
}最后
即使感知自己身體的需求，不管是體力消耗還是腦力消耗，及時補充能量，吃飯，休息。
