今年又開始了，今天主要是總結(jié)上兩周的做題記錄，這幾天還是有點放松，懈怠了，必須要抓緊了

上周主要完成了簡單的二叉樹算法題

二叉樹的中序遍歷

這題主要是開始復(fù)習二叉樹的遍歷，需要學(xué)習的知識分別是二叉樹的前序，中序，以及后序遍歷，同時需要關(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
}