Go教程

go 刷算法第三题——二叉树根节点到叶子节点和为指定值的路径

本文主要是介绍go 刷算法第三题——二叉树根节点到叶子节点和为指定值的路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

image

思路

穷举所有叶子节点,判断是否满足条件。

go代码

package main

import "fmt"

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

func demo(root *TreeNode, sum int, path []int, result *[][]int) {
	if root.Left != nil {
		demo(root.Left, sum-root.Val, append(path, root.Val), result)
	}
	if root.Right != nil {
		demo(root.Right, sum-root.Val, append(path, root.Val), result)
	}
	// 为叶子节点,递归结束。判断 root.Val == sum
	if root.Left == nil && root.Right == nil && root.Val == sum {
		// 由于闭包的原因,在root.Val==A的时候,A的右子节点递归与A的左子节点递归传递的path是同一个引用地址。
		// *result = append(*result, append(path, sum))
		tmp := make([]int, len(path)+1)
		copy(tmp, append(path, sum))
		*result = append(*result, tmp)
	}
}

func pathSum(root *TreeNode, sum int) [][]int {
	if root == nil {
		return nil
	}
	result := make([][]int, 0)
	path := make([]int, 0)
	demo(root, sum, path, &result)
	fmt.Println(result)
	return result
}

func main() {
	//node := TreeNode{1, &TreeNode{2, nil, nil}, nil}
	node := TreeNode{1, nil, nil}
	sum := pathSum(&node, 1)
	fmt.Println(sum)
}

这篇关于go 刷算法第三题——二叉树根节点到叶子节点和为指定值的路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!