目录

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 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

代码：

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func hasPathSum(root *TreeNode, targetSum int) bool {sum := func(arr []int) int {res := 0for i := 0; i < len(arr); i++ {res += arr[i]}return res}for _, path := range binaryTreePaths(root) {if sum(path) == targetSum {return true}}return false
}func binaryTreePaths(root *TreeNode) [][]int {res := [][]int{}if root == nil {return res}if root.Left == nil && root.Right == nil {return [][]int{{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 := 1for 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{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}root := buildTree(nums)fmt.Println(hasPathSum(root, 22))nums2 := []int{1, 2, 3}root = buildTree(nums2)fmt.Println(hasPathSum(root, 5))nums3 := []int{}root = buildTree(nums3)fmt.Println(hasPathSum(root, 0))
}

输出：

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 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

代码：

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func pathSum(root *TreeNode, targetSum int) [][]int {res := [][]int{}sum := func(arr []int) int {res := 0for i := 0; i < len(arr); i++ {res += arr[i]}return res}for _, path := range binaryTreePaths(root) {if sum(path) == targetSum {res = append(res, append([]int{}, path...))}}return res
}func binaryTreePaths(root *TreeNode) [][]int {res := [][]int{}if root == nil {return res}if root.Left == nil && root.Right == nil {return [][]int{{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 := 1for 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{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}root := buildTree(nums)fmt.Println(pathSum(root, 22))nums2 := []int{1, 2, 3}root = buildTree(nums2)fmt.Println(pathSum(root, 5))nums3 := []int{1, 2}root = buildTree(nums3)fmt.Println(pathSum(root, 0))
}

输出：

[[5 4 11 2] [5 8 4 5]]
[]
[]

以上两题都用到了遍历出所有路径的函数 func binaryTreePaths(root *TreeNode) [][]int

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func binaryTreePaths(root *TreeNode) [][]int {res := [][]int{}if root == nil {return res}if root.Left == nil && root.Right == nil {return [][]int{{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 := 1for 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{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}root := buildTree(nums)fmt.Println(binaryTreePaths(root))
}

 输出：

[[5 4 11 7] [5 4 11 2] [5 8 13] [5 8 4 5] [5 8 4 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 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

代码：

func flatten(root *TreeNode) {
list, cur := []int{}, &TreeNode{}
preorder(root, &list)
cur = root
for i := 1; i < len(list); i++ {
cur.Left = nil
cur.Right = &TreeNode{Val: list[i], Left: nil, Right: nil}
cur = cur.Right
}
return
}func flatten1(root *TreeNode) {
if root == nil || (root.Left == nil && root.Right == nil) {
return
}
flatten(root.Left)
flatten(root.Right)
currRight := root.Right
root.Right = root.Left
root.Left = nil
for root.Right != nil {
root = root.Right
}
root.Right = currRight
}

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏