题解 | #二叉树的中序遍历#

//golang解法

package main

import "fmt"

/**
 * Created by Chris on 2021/8/3.
 */

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

func pathSum(root *TreeNode,  sum int) [][]int {
	if root == nil{
		return [][]int{}
	}
	//存放结果
	var res [][]int
	//暂存当前路径
	var temp []int
	//深度优先搜索
	dfs(sum, &res, temp, root)
	return res
}

func dfs(sum int, res *[][]int, temp []int, node *TreeNode){
	//遇到空节点
	if node == nil{
		return
	}
	//记录路径：添加当前节点
	temp = append(temp, node.Val)
	sum -= node.Val
	//遇到叶子节点
	if node.Left == nil && node.Right == nil && sum == 0{
		//创建新的切片，用于保存当前路径。
		//不可以直接使用：*res = append(*res, temp)，这是引用了temp中的数据，没有复制temp中的数据。
		tempRes := append([]int(nil), temp...)
		*res = append(*res, tempRes)
	}
	//递归
	dfs(sum, res, temp, node.Left)
	dfs(sum, res, temp, node.Right)
	//去除节点
	temp = temp[:len(temp) - 1]
}

func main() {
	var node1 = &TreeNode{5, nil, nil}
	var node2 = &TreeNode{4, nil, nil}
	var node3 = &TreeNode{8, nil, nil}
	var node4 = &TreeNode{1, nil, nil}
	var node5 = &TreeNode{11, nil, nil}
	var node6 = &TreeNode{9, nil, nil}
	var node7 = &TreeNode{2, nil, nil}
	var node8 = &TreeNode{7, nil, nil}

	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Right = node6
	node5.Left = node7
	node5.Right = node8

	var sum int = 22
	var res [][]int = pathSum(node1, sum)
	fmt.Println(res)
}