257. 二叉树的所有路径 Binary-tree Paths
给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]
示例 2:
输入:root = [1]
输出:["1"]
提示:
- 树中节点的数目在范围
[1, 100]
内 -100 <= Node.val <= 100
代码1:
遍历出所有路径,再改写字符串数组。参见:
Golang每日一练(leetDay0038) 二叉树专题(7)路径总和I\II
package main import ( "fmt" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func binaryTreePaths(root *TreeNode) []string { res := []string{} paths := PathsLists(root) if len(paths) == 0 { return res } for _, path := range paths { res = append(res, getPath(path)) } return res } func getPath(path []int) string { var res string for i := 0; i < len(path)-1; i++ { res += fmt.Sprintf("%d", path[i]) + "->" } res += fmt.Sprintf("%d", path[len(path)-1]) return res } func PathsLists(root *TreeNode) [][]int { res := [][]int{} if root == nil { return res } if root.Left == nil && root.Right == nil { return [][]int{{root.Val}} } leftPaths := PathsLists(root.Left) rightPaths := PathsLists(root.Right) paths := make([][]int, 0) for _, path := range leftPaths { paths = append(paths, append([]int{root.Val}, path...)) } for _, path := range rightPaths { paths = append(paths, append([]int{root.Val}, path...)) } return paths } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func main() { nums := []int{1, 2, 3, null, 5} root := buildTree(nums) fmt.Println(binaryTreePaths(root)) nums = []int{1} root = buildTree(nums) fmt.Println(binaryTreePaths(root)) }
输出:
[1->2->5 1->3]
[1]
代码2: DFS
package main import ( "fmt" "strconv" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func binaryTreePaths(root *TreeNode) []string { var res []string if root == nil { return res } var path []string dfs(&res, path, root) return res } func dfs(res *[]string, path []string, node *TreeNode) { path = append(path, strconv.Itoa(node.Val)) if node.Left == nil && node.Right == nil { *res = append(*res, getPath(path)) return } if node.Left != nil { dfs(res, path, node.Left) } if node.Right != nil { dfs(res, path, node.Right) } } func getPath(path []string) string { var res string for i := 0; i < len(path)-1; i++ { res += path[i] + "->" } res += path[len(path)-1] return res } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func main() { nums := []int{1, 2, 3, null, 5} root := buildTree(nums) fmt.Println(binaryTreePaths(root)) nums = []int{1} root = buildTree(nums) fmt.Println(binaryTreePaths(root)) }
258. 各位相加 Add Digits
给定一个非负整数 num
,反复将各个位上的数字相加,直到结果为一位数。返回这个结果。
示例 1:
输入: num =38
输出: 2
解释: 各位相加的过程为:
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数,所以返回 2。
示例 1:
输入: num =0
输出: 0
提示:
0 <= num <= 2^31 - 1
进阶:你可以不使用循环或者递归,在 O(1)
时间复杂度内解决这个问题吗?
代码: 4种方法
package main import "fmt" func addDigits(num int) int { if num < 10 { return num } sum := 0 for num > 0 { sum += num % 10 num /= 10 } return addDigits(sum) } func addDigits2(num int) int { for num >= 10 { sum := 0 for num > 0 { sum += num % 10 num /= 10 } num = sum } return num } func addDigits3(num int) int { if num == 0 { return 0 } else if num % 9 == 0 { return 9 } else { return num % 9 } } func addDigits4(num int) int { return (num - 1) % 9 + 1 } func main() { num := 38 fmt.Println(addDigits(num)) fmt.Println(addDigits2(num)) fmt.Println(addDigits3(num)) fmt.Println(addDigits4(num)) num = 0 fmt.Println(addDigits(num)) fmt.Println(addDigits2(num)) fmt.Println(addDigits3(num)) fmt.Println(addDigits4(num)) }
输出:
2
2
2
2
0
0
0
0
🌟 每日一练刷题专栏 🌟
✨持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
Rust每日一练 专栏 (2023.5.16~)更新中... |
|
Golang每日一练 专栏 (2023.3.11~)更新中... |
|
Python每日一练 专栏 (2023.2.18~2023.5.18)暂停更 |
|
C/C++每日一练 专栏 (2023.2.18~2023.5.18)暂停更 |
|
Java每日一练 专栏 (2023.3.11~2023.5.18)暂停更 |