(23)Go递归求二叉树各类路径问题2

继上篇《(22)Go递归求二叉树各类路径问题1》https://www.jianshu.com/p/7b85290659a6

问题4：求二叉树指定路径 //

方法1：从上往下添加路径
测试结果速度100,内存6.67,速度可以但太耗费内存，方法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 {
            // 做一次复制
            buf := append([]int{}, arr...)
            f(t.Left, sum-t.Val, buf)
        }

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

    f(root, sum, arrs)
    return res
}

方法1提交leetcode，通过

方法2：从下往上添加路径，leetcode上优秀解答，作者未知，思路很棒
// 做了一点小修改
func pathSum2(root *TreeNode, sum int) [][]int {
    // 递归终止条件
    if root == nil {
        return [][]int{}
    }

    // 递归过程
    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个成立,就会执行这一步,一直往上加,
    // 相比方法1少了很多添加路径和复制的操作
    // 如果这一步没执行,说明左右都没有成立的,返回的tatal是空的
    if len(total) > 0 {
        rootInt := []int{root.Val}
        for i := range total {
            total[i] = append(rootInt, total[i]...)
        }
    }
    return total
}

方法2的测试结果

问题5：找特定子路径 //

思路如下图示：

// 注意2个函数的区别，1个包含根节点，一个不必要包含根节点
// 在root为根节点的二叉树中,寻找sum的路径,返回路径个数
func pathSum(root *TreeNode, sum int) int {
    // 递归终止条件
    if root == nil {
        return 0
    }

    // 递归过程
    // res:符合条件的路径数量
    res := findPath(root, sum)
    res += pathSum(root.Left, sum) + pathSum(root.Right, sum)
    return res
}

// 在以t为根节点的二叉树中,寻找包含t的路径,和为sum的路径总数
// 返回路径个数(和上面对比,1个路径不包含根节点,一个包含根节点)
func findPath(t *TreeNode, sum int) int {
    // 递归终止条件
    if t == nil {
        return 0
    }

    // 递归过程
    // res:符合条件的路径数量
    res := 0
    if sum == t.Val {
        res++
    }

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

提交leetcode，通过

问题6：求两点近公共祖先 //

思路：这个问题的难点在于弄清公共祖先的情况：
给定的2个点必须同时满足小于根节点，或者大于根节点，不然该根节点就是这2节点的最近公共祖先
弄明白这情况代码就好写很多
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 递归终止条件
    if root == nil {
        return nil
    }

    // 递归过程
    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)
    }

    // 这里有个小bug,如果p, q不存在树中且最后在叶子节点达到这一步,
    // 那返回这个叶子节点,显然叶子节点是不可能成为公共祖先的，
    // 严谨一点要再去判断下p,q是否存在树中
    return root
}

提交leetcode，通过

有bug欢迎指出