每日一题
二叉树的所有路径
跳转链接
![二叉树的所有路径](https://img.helloteemo.com.cn/2022/11/17/1668674149.png)
二叉树的解题思路:
- 确定终止条件
- 确定递归姿势
- 递归条件
这里需要获取二叉树的所有路径,案例:
![image-20221117163806253](https://img.helloteemo.com.cn/2022/11/17/1668674288.png)
一个空节点的所有路径就是空的,而一个不存在子节点的节点的所有路径就是它自己。按照这个我们就可以确定终止条件了
因为是要获取二叉树的所有路径,那么肯定是先使用根节点了,所有使用的是前序遍历
我们想象一下只有三个节点如何获取所有路径呢?拿根节点加上左右节点的所有路径就可以啦,也就是1->2,1->3。这也就是它的递归条件
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| func binaryTreePaths(root *TreeNode) []string { if root == nil { return nil } if root.Right == nil && root.Left == nil { return []string{strconv.Itoa(root.Val)} }
var res = make([]string, 0, 2) if root.Left != nil { treePaths := binaryTreePaths(root.Left) for _, path := range treePaths { res = append(res, fmt.Sprintf("%d->%s", root.Val, path)) } } if root.Right != nil { treePaths := binaryTreePaths(root.Right) for _, path := range treePaths { res = append(res, fmt.Sprintf("%d->%s", root.Val, path)) } }
return res }
|