2020-04-12 aa7c15906b1232b6c67044da0aecbcff 99+ 2 分钟 0.2 k 0次访问

剑指offer-二叉树中和为某一值的路径

一、题意

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径

二、分析

由于路径是从根结点出发到叶结点，也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。
当用前序遍历的方式访问到某一结点时，我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。
如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。
因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根结点到父结点的路径。

三、参考Leetcode原题

113. Path Sum II

四、代码实现

>folded main.go

package main

import (
	"fmt"
)

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

func FindPath(root *TreeNode, sum int) {
	if root == nil || root.Data == 0 || root.Left == nil || root.Right == nil {
		return
	}

	var path []int
	cursum := 0
	findPath(root, sum, path, cursum)
	fmt.Println("------")
	fmt.Println(path)
	fmt.Println(cursum)
}

func findPath(root *TreeNode, sum int, path []int, cursum int) {
	cursum += root.Data
	path = append(path, root.Data)

	// 如果是叶子节点，且路径上节点的和等于输入的值
	// 打印出这条路径
	leaf := root.Left == nil && root.Right == nil
	if cursum == sum && leaf {
		fmt.Print("a path is found: ")
		for i := 0; i < len(path); i++ {
			fmt.Printf("%d --> ", path[i])
		}
		fmt.Println()
	}

	// 如果不是叶子节点，则遍历它的子节点
	if root.Left != nil {
		findPath(root.Left, sum, path, cursum)
	}
	if root.Right != nil {
		findPath(root.Right, sum, path, cursum)
	}

	// 在返回到父节点之前，在路径上删除当前节点，
	// 并在cursum中减去当前节点的值
	cursum -= root.Data
	path = path[:len(path)-1]
	fmt.Println(cursum)
	fmt.Println(path)
}

func main() {
	node4 := &TreeNode{4, nil, nil}
	node7 := &TreeNode{7, nil, nil}
	node5 := &TreeNode{5, node4, node7}
	node12 := &TreeNode{12, nil, nil}
	node10 := &TreeNode{10, node5, node12}
	FindPath(node10, 22)
}

// 输出
19
[10 5 4]
a path is found: 10 --> 5 --> 7 --> 
22
[10 5 7]
15
[10 5]
a path is found: 10 --> 12 --> 
22
[10 12]
10
[10]
------
[]
0

Process finished with exit code 0