(22)Go递归求二叉树各类路径问题1
2019-05-14 本文已影响0人
哥斯拉啊啊啊哦
问题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欢迎指出