[Day33-01]-[二叉树] 路径总和

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：[[5,4,11,2],[5,8,4,5]]

输入：root = [1,2,3], targetSum = 5输出：[]

输入：root = [1,2], targetSum = 0输出：[]

func TestPathSum(t *testing.T) {	var root = &TreeNode{		Val: 5,		Left: &TreeNode{			Val: 4,			Left: &TreeNode{				Val: 11,				Left: &TreeNode{					Val: 7,				},				Right: &TreeNode{					Val: 2,				},			},		},		Right: &TreeNode{			Val: 8,			Left: &TreeNode{				Val: 13,			},			Right: &TreeNode{				Val: 4,				Left: &TreeNode{					Val: 5,				},				Right: &TreeNode{					Val: 1,				},			},		},	}	var targetSum = 22	var routes = [][]int{}	var path = []int{}	var dfs func(root *TreeNode, sum int) // DLR 遍历	dfs = func(root *TreeNode, sum int) {		if root == nil { // 递归终止条件			return		}		path = append(path, root.Val) // 将值放入到路径中		defer func() {                // 每次回溯结束的时候哦回到上个位置			path = path[:len(path)-1]		}()		sum += root.Val                                                // 累加值		if root.Left == nil && root.Right == nil && sum == targetSum { // 到达叶子节点的时候处理逻辑			// routes = append(routes, path) 这种写法是错误的是，这种复制是按引用复制，path如果修改会影响route			routes = append(routes, append([]int{}, path...)) // 按值复制 或者 copy 深度复制		}		dfs(root.Left, sum)		dfs(root.Right, sum)	}	dfs(root, 0)	t.Log(routes)}

func TestPathSum(t *testing.T) {	var root = &TreeNode{		Val: 5,		Left: &TreeNode{			Val: 4,			Left: &TreeNode{				Val: 11,				Left: &TreeNode{					Val: 7,				},				Right: &TreeNode{					Val: 2,				},			},		},		Right: &TreeNode{			Val: 8,			Left: &TreeNode{				Val: 13,			},			Right: &TreeNode{				Val: 4,				Left: &TreeNode{					Val: 5,				},				Right: &TreeNode{					Val: 1,				},			},		},	}	var routes = [][]int{}	var targetSum = 22	var dfs func(root *TreeNode, path []int, sum int)	dfs = func(root *TreeNode, path []int, sum int) {		if root == nil {			return		}		path = append(path, root.Val)		sum += root.Val		if root.Left == nil && root.Right == nil {			if sum == targetSum {				tmp := make([]int, len(path))				copy(tmp, path)				routes = append(routes, tmp)			}		}		dfs(root.Left, path, sum)		dfs(root.Right, path, sum)	}	dfs(root, []int{}, 0)	t.Log(routes)}