目录
112. 路径总和 Path Sum 🌟
113. 路径总和 II Path Sum II 🌟🌟
114. 二叉树展开为链表 Flatten Binary Tree to Linked-list 🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
二叉树专题（7）
112. 路径总和 Path Sum
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000-1000
代码：
package main
import (
"fmt"
)
const null = -1 {root.Val}}
}
leftPaths := binaryTreePaths(root.Left)
rightPaths := binaryTreePaths(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 输出：
true
false
false
113. 路径总和 II Path Sum II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000-1000
代码1：
package main
import (
"fmt"
)
const null = -1 {root.Val}}
}
leftPaths := binaryTreePaths(root.Left)
rightPaths := binaryTreePaths(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 输出：
[[5 4 11 2] [5 8 4 5]]
[]
[]
以上两题都用到了遍历出所有路径的函数 func binaryTreePaths(root *TreeNode) [][]int
package main
import (
"fmt"
)
const null = -1 {root.Val}}
}
leftPaths := binaryTreePaths(root.Left)
rightPaths := binaryTreePaths(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 输出：
[[5 4 11 7] [5 4 11 2] [5 8 13] [5 8 4 5] [5 8 4 1]]
方法2： 递归 DFS
package main
import "fmt"
const null = -1 114. 二叉树展开为链表 Flatten Binary Tree to Linked-list
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
- 树中结点数在范围
[0, 2000]内 -100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
代码：
func flatten(root *TreeNode) {
list, cur := []int{}, &TreeNode{}
preorder(root, &list)
cur = root
for i := 1; i 🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 |
Golang每日一练 专栏
|
 |
Python每日一练 专栏
|
 |
C/C++每日一练 专栏
|
 |
Java每日一练 专栏
|
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
