繼上篇《(22)Go遞歸求二叉樹各類路徑問題1》http://www.reibang.com/p/7b85290659a6

問題4：求二叉樹指定路徑 //

方法1：從上往下添加路徑
測(cè)試結(jié)果速度100,內(nèi)存6.67,速度可以但太耗費(fèi)內(nèi)存代兵，方法2更加快
func pathSum(root *TreeNode, sum int) [][]int {
    res := [][]int{}
    arrs := []int{}

    var f func(t *TreeNode, sum int, arr []int)
    f = func(t *TreeNode, sum int, arr []int) {
        if t == nil {
            return
        }

        arr = append(arr, t.Val)
        if t.Val == sum && t.Left == nil && t.Right == nil {
            res = append(res, arr)
            return
        }

        if t.Left != nil {
            // 做一次復(fù)制
            buf := append([]int{}, arr...)
            f(t.Left, sum-t.Val, buf)
        }

        if t.Right != nil {
            // 做一次復(fù)制
            buf := append([]int{}, arr...)
            f(t.Right, sum-t.Val, buf)
        }
    }

    f(root, sum, arrs)
    return res
}

方法1提交leetcode宋列，通過(guò)

方法2：從下往上添加路徑，leetcode上優(yōu)秀解答但荤，作者未知，思路很棒
// 做了一點(diǎn)小修改
func pathSum2(root *TreeNode, sum int) [][]int {
    // 遞歸終止條件
    if root == nil {
        return [][]int{}
    }

    // 遞歸過(guò)程
    if sum == root.Val && root.Left == nil && root.Right == nil {
        return [][]int{[]int{sum}}
    }

    sum -= root.Val
    left, right := [][]int{}, [][]int{}

    if root.Left != nil {
        left = pathSum2(root.Left, sum)
    }
    if root.Right != nil {
        right = pathSum2(root.Right, sum)
    }
    total := append(left, right...)

    // 精髓1:只要最終左右有1個(gè)成立,就會(huì)執(zhí)行這一步,一直往上加,
    // 相比方法1少了很多添加路徑和復(fù)制的操作
    // 如果這一步?jīng)]執(zhí)行,說(shuō)明左右都沒有成立的,返回的tatal是空的
    if len(total) > 0 {
        rootInt := []int{root.Val}
        for i := range total {
            total[i] = append(rootInt, total[i]...)
        }
    }
    return total
}

方法2的測(cè)試結(jié)果

問題5：找特定子路徑 //

思路如下圖示：

// 注意2個(gè)函數(shù)的區(qū)別，1個(gè)包含根節(jié)點(diǎn)爹梁，一個(gè)不必要包含根節(jié)點(diǎn)
// 在root為根節(jié)點(diǎn)的二叉樹中,尋找sum的路徑,返回路徑個(gè)數(shù)
func pathSum(root *TreeNode, sum int) int {
    // 遞歸終止條件
    if root == nil {
        return 0
    }

    // 遞歸過(guò)程
    // res:符合條件的路徑數(shù)量
    res := findPath(root, sum)
    res += pathSum(root.Left, sum) + pathSum(root.Right, sum)
    return res
}

// 在以t為根節(jié)點(diǎn)的二叉樹中,尋找包含t的路徑,和為sum的路徑總數(shù)
// 返回路徑個(gè)數(shù)(和上面對(duì)比,1個(gè)路徑不包含根節(jié)點(diǎn),一個(gè)包含根節(jié)點(diǎn))
func findPath(t *TreeNode, sum int) int {
    // 遞歸終止條件
    if t == nil {
        return 0
    }

    // 遞歸過(guò)程
    // res:符合條件的路徑數(shù)量
    res := 0
    if sum == t.Val {
        res++
    }

    res += findPath(t.Left, sum-t.Val) + findPath(t.Right, sum-t.Val)
    return res
}

提交leetcode，通過(guò)

問題6：求兩點(diǎn)近公共祖先 //

思路：這個(gè)問題的難點(diǎn)在于弄清公共祖先的情況：
給定的2個(gè)點(diǎn)必須同時(shí)滿足小于根節(jié)點(diǎn)提澎，或者大于根節(jié)點(diǎn)姚垃，不然該根節(jié)點(diǎn)就是這2節(jié)點(diǎn)的最近公共祖先
弄明白這情況代碼就好寫很多
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 遞歸終止條件
    if root == nil {
        return nil
    }

    // 遞歸過(guò)程
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    } else if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }

    // 這里有個(gè)小bug,如果p, q不存在樹中且最后在葉子節(jié)點(diǎn)達(dá)到這一步,
    // 那返回這個(gè)葉子節(jié)點(diǎn),顯然葉子節(jié)點(diǎn)是不可能成為公共祖先的，
    // 嚴(yán)謹(jǐn)一點(diǎn)要再去判斷下p,q是否存在樹中
    return root
}

提交leetcode盼忌，通過(guò)

有bug歡迎指出