提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Golang每日一练(leetDay0038) 二叉树专题（7）

二叉树Golang 每日 专题
2023-09-14 09:01:28 时间

目录

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 main

import (
	"fmt"
)

const null = -1 << 31

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func hasPathSum(root *TreeNode, targetSum int) bool {
	sum := func(arr []int) int {
		res := 0
		for 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 := 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{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

代码1：

package main

import (
	"fmt"
)

const null = -1 << 31

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func pathSum(root *TreeNode, targetSum int) [][]int {
	res := [][]int{}
	sum := func(arr []int) int {
		res := 0
		for 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 := 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{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 main

import (
	"fmt"
)

const null = -1 << 31

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *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 := 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{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]]

方法2： 递归 DFS

package main

import "fmt"

const null = -1 << 31 // 用Math.MinInt32来表示空节点

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

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 pathSum(root *TreeNode, targetSum int) [][]int {
	result := [][]int{}
	if root == nil {
		return result
	}
	path := []int{}
	dfs(root, targetSum, path, &result)
	return result
}

func dfs(node *TreeNode, targetSum int, path []int, res *[][]int) {
	if node == nil {
		return
	}
	path = append(path, node.Val)
	if node.Left == nil && node.Right == nil && node.Val == targetSum {
		temp := make([]int, len(path))
		copy(temp, path)
		*res = append(*res, temp)
		return
	}
	dfs(node.Left, targetSum-node.Val, path, res)
	dfs(node.Right, targetSum-node.Val, path, res)
	path = path[:len(path)-1]
}

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))
}

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每日一练 专栏

相关文章