(22)Go递归求二叉树各类路径问题1

问题1：路径总和 //

// 路径总和 (注意叶子节点的定义)
func hasPathSum(root *TreeNode, sum int) bool {
    // 递归终止条件
    if root == nil {
        return false
    }

    // 递归过程
    // 判断该节点是否叶子节点
    if sum == root.Val && root.Left == nil && root.Right == nil {
        return true
    }

    // 只要有1边成立,返回true,两边都不成立,返回false
    return hasPathSum(root.Left, sum-root.Val) ||
        hasPathSum(root.Right, sum-root.Val)
}

提交leetcode，通过

问题2：左叶子节点之和 //

func sumOfLeftLeaves(root *TreeNode) int {
    // 递归终止条件
    if root == nil {
        return 0
    }

    // 递归终止条件
    // 判断是不是左叶子节点
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        return root.Left.Val + sumOfLeftLeaves(root.Right)
    }

    // 4种情况,都可以用同一个表达式表达，理解好这点代码简洁很多
    // 左nil,返回0+sum(right);
    // 右nil,返回0+sum(left);
    // 左右nil,返回0+0
    // 左右不为nil,返回sum(left)+sum(right)
    return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}

提交leetcode，通过

问题3：求所有根节点到叶子节点的路径 //

思路如下图示

方法1
func binaryTreePaths(root *TreeNode) []string {
    // 递归终止条件
    if root == nil {
        return nil
    }

    // 递归过程
    str := strconv.Itoa(root.Val)
    res := []string{}
    if root.Left == nil && root.Right == nil {
        res = []string{str}
    }

    str = str + "->"
    buf1 := binaryTreePaths(root.Left)
    // 自身值加左子树所有路径
    for i := 0; i < len(buf1); i++ {
        res = append(res, str+buf1[i])
    }

    buf1 = binaryTreePaths(root.Right)
    // 自身值加右子树所有路径
    for i := 0; i < len(buf1); i++ {
        res = append(res, str+buf1[i])
    }
    return res
}

方法2，leetcode上的，作者未知，代码看起来比我的更简洁易懂
func binaryTreePaths2(root *TreeNode) []string {
    paths := []string{}

    var f func(t *TreeNode, str string)
    f = func(t *TreeNode, str string) {
        // 递归终止条件
        if t == nil {
            return
        }

        // 递归过程
        str = str + "->" + strconv.Itoa(t.Val)
        if t.Left == nil && t.Right == nil {
            // 前两位是"->",根节点前面加"->"可以统一逻辑
            paths = append(paths, str[2:])
        }

        if t.Left != nil {
            f(t.Left, str)
        }
        if t.Right != nil {
            f(t.Right, str)
        }
    }

    f(root, "")
    return paths
}

方法1提交leetcode，通过

继下篇《(23)Go递归求二叉树各类路径问题2》https://www.jianshu.com/p/07fb3f4bea13

有bug欢迎指出

最后编辑于：2020.09.18 01:58:32