题目概述

• 算法说明
  输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
• 测试用例
  输入1：
  {10,5,12,4,7},22
  输出1：
  [[10,5,7],[10,12]]
  输入2：
  {10,5,12,4,7},15
  输出2：
  []

解析&参考答案

• 解析

1. 使用递归的方式，每次从根节点出发，每次递归的时候其sum减对应的节点值，sum值为0且该节点刚好为叶子节点的时候，该路径就满足要求；

• 参考答案

vim jz24.go
package main

import "fmt"

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

func FindPath(root *TreeNode, expectNumber int) [][]int {
	result := make([][]int, 0)
	res := make([]int, 0)
	FindPathCore(root, expectNumber, res, &result)
	return result
}

func FindPathCore(root *TreeNode, expectNumber int, res []int, result *[][]int) {
	if root == nil {
		return
	}
	expectNumber -= root.Val
	res = append(res, root.Val)
	if expectNumber == 0 && root.Left == nil && root.Right == nil {
		*result = append(*result, res)
	} else {
		FindPathCore(root.Left, expectNumber, res, result)
		FindPathCore(root.Right, expectNumber, res, result)
	}
	res = res[:len(res)-1]
}

func main() {
	root := &TreeNode{10, &TreeNode{5, &TreeNode{4, nil, nil}, &TreeNode{7, nil, nil}},
		&TreeNode{12, nil, nil}}
	expectNumber := 22 // 15
	ret := FindPath(root, expectNumber)
	fmt.Println(ret)
}

注意事项

1. 每次递归结束后需要去掉加入到res数组中最后一个元素。

说明

1. 当前使用 go1.15.8
2. 参考 牛客网--剑指offer
   标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目，例如 jz01 代表牛客网剑指offer中01号题目。

注意!!!

• 笔者最近在学习 golang，因此趁机通过数据结构和算法来进一步熟悉下go语言
• 当前算法主要来源于剑指 offer，后续会进一步补充 LeetCode 上重要算法，以及一些经典算法
• 此处答案仅为参考，不一定是最优解，欢迎感兴趣的读者在评论区提供更优解