今年又開始了举哟，今天主要是總結(jié)上兩周的做題記錄，這幾天還是有點放松，懈怠了敞临，必須要抓緊了
上周主要完成了簡單的二叉樹算法題
二叉樹的中序遍歷
這題主要是開始復(fù)習(xí)二叉樹的遍歷，需要學(xué)習(xí)的知識分別是二叉樹的前序麸澜，中序挺尿，以及后序遍歷，同時需要關(guān)注針對遞歸返回的數(shù)組怎么處理
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
if root == nil{
return nil
}
var ret []int
if root.Left != nil{
ret = append(ret,inorderTraversal(root.Left)...)
}
ret = append(ret,root.Val)
if root.Right != nil{
ret = append(ret,inorderTraversal(root.Right)...)
}
return ret
}
相同的樹
這題一樣也就比較簡單了炊邦，之前會先思考通過遍歷的方式编矾，獲取到一個數(shù)組，然后判斷兩個數(shù)組是否相等
但是同樣的铣耘，可以通過遞歸進行處理洽沟，這題就和鏡像樹的邏輯大同小異了
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil{
return true
}
if p == nil || q == nil{
return false
}
if p.Val != q.Val{
return false
}
return isSameTree(p.Left,q.Left)&&isSameTree(p.Right,q.Right)
}
翻轉(zhuǎn)二叉樹
這題還是比較看重結(jié)題思路的，優(yōu)先演繹一下怎么進行翻轉(zhuǎn)蜗细，可以發(fā)現(xiàn)裆操，通過交換每個根節(jié)點的左右的節(jié)點，就能實現(xiàn)對二叉樹的翻轉(zhuǎn)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil{
return root
}
if root.Left == nil && root.Right==nil{
return root
}
var ret = root.Left
root.Left = root.Right
root.Right = ret
invertTree(root.Left)
invertTree(root.Right)
return root
}
叉樹的最大最小深度
最小深度因為需要考慮空節(jié)點的情況炉媒，所以邊界條件較多
當根節(jié)點有一個為子節(jié)點為空的情況下踪区，應(yīng)該返回較大的節(jié)點數(shù)
當根節(jié)點兩個子節(jié)點都為空的情況下，直接返回0
當根節(jié)點兩個子節(jié)點都不為空的情況下吊骤，直接返回較小的
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil{
return 0
}
lDepth := minDepth(root.Left)
rDepth := minDepth(root.Right)
if lDepth == 0{
return rDepth +1
}
if rDepth == 0{
return lDepth +1
}
if lDepth <= rDepth {
return lDepth+1
}
return rDepth + 1
}
最大深度不需要考慮結(jié)果的邊界情況
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
if root == nil{
return 0
}
leftRet := maxDepth(root.Left)
rightRet := maxDepth(root.Right)
if leftRet+1 >=rightRet+1{
return leftRet+1
}
return rightRet+1
}
將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
結(jié)束條件為左大于右的情況下
處理的邏輯為為左右節(jié)點賦值
這題也是需要思路的缎岗，還是要經(jīng)過事先的演繹進行推導(dǎo)，通過使用二分法白粉，中間節(jié)點為根節(jié)點
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
if nums == nil{
return nil
}
return helper(nums,0,len(nums)-1)
}
func helper(nums []int,left ,right int)*TreeNode{
if left > right{
return nil
}
var (
mid = (left + right)/2
root TreeNode
)
root.Val = nums[mid]
root.Left = helper(nums,left,mid -1)
root.Right = helper(nums,mid+1,right)
return &root
}
路徑總和
遞歸法 退出邏輯：當當前節(jié)點為的左右節(jié)點為空同時當前值==剩余值
處理邏輯 遍歷左右節(jié)點传泊，分別-根節(jié)點值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil{
return false
}
if root.Left ==nil&& root.Right == nil &&targetSum-root.Val == 0{
return true
}
if hasPathSum(root.Left,targetSum - root.Val){
return true
}
if hasPathSum(root.Right,targetSum-root.Val){
return true
}
return false
}
