根据输入构建完全二叉树， 并找出根到节点和为给定值的所有路径

​
package main

import (
    "fmt"
    "strings"
    "strconv"
)


type Node struct {
	Data int
	Left *Node
	Right *Node
	High int
}

func main() {
	// 根据输入构建完全二叉树， 并找出根到节点和为给定值的所有路径
	// 输入
	// 22
	// 10,5,12,4,7	
	// 输出
	// 10,5,7
	// 10,12
	//
	// 使用栈对树进行深度优先遍历，利用树高更方便寻找判断路径
	paths, err := findPath(22, "10,5,12,4,7")
	fmt.Println(paths, err)
	
}
// 查找路径
func findPath(sum int, nodeVals string) (paths [][]int, err error) {
	var tmpVals []int
	vals := strings.Split(nodeVals, ",")
	for _, v := range vals{
		v2, err := strconv.Atoi(v)
		if err != nil {
			continue 
		}
		tmpVals = append(tmpVals, v2)
	}
	
	head, err := bulidTree(tmpVals)
	if err != nil {
		return 
	}
	var stack []*Node
	var tmpNode *Node
	var path []int
	stack = append(stack, head)

	for {
		length := len(stack)
		if length == 0 {
			break
		}
		tmpNode = stack[length-1]
		stack = stack[:length-1]
		if len(path) > 0 {
			path = path[:tmpNode.High]
		}
		path = append(path, tmpNode.Data)
		if checkPath(path, sum) {
			paths = append(paths, path) 
		}
		if tmpNode.Right != nil {
			stack = append(stack, tmpNode.Right) 
		}
		if tmpNode.Left != nil {
			stack = append(stack, tmpNode.Left) 
		}
	}
	return 
}
// 校验路径
func checkPath(path []int, sum int) (b bool) {
	b = false
	if len(path) == 0 {
		return 
	}
	var s int
	for _, v := range path {
		s += v
	}
	return sum == s
}

// 构建完全二叉树 [10,5,12,4,7,8,9,11,13]
func bulidTree(vals []int) (*Node, error) {
	length := len(vals)
	if length <=0 {
		return nil, fmt.Errorf("empty node")
	}
	var head, tmpNode *Node
	var brotherNodeList []*Node
	for _, v := range vals{
		node := &Node{Data: v}
		if head == nil {
			head = node
			tmpNode = node
		}else{
			brotherNodeList = append(brotherNodeList, node)
			node.High = tmpNode.High + 1
			if tmpNode.Left == nil {
				tmpNode.Left = node
			} else if tmpNode.Right == nil{
				tmpNode.Right = node
				tmpNode = brotherNodeList[0]
				brotherNodeList = brotherNodeList[1:]
			}
		}
	}
	return head, nil
}

​

有疑问加站长微信联系（非本文作者）