go acm模式 二叉树

输入前序

package main

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

// 定义树节点结构
type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

// 构建二叉树
func buildTree(values []string) (*TreeNode, int) {
	if len(values) == 0 || values[0] == "null" {
		return nil, 1
	}
	val, _ := strconv.Atoi(values[0])
	node := &TreeNode{val: val}
	leftChild, leftCount := buildTree(values[1:])
	rightChild, rightCount := buildTree(values[1+leftCount:])
	node.left = leftChild
	node.right = rightChild
	return node, 1 + leftCount + rightCount
}

// 判断是否存在满足条件的路径
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.left == nil && root.right == nil {
		return targetSum == root.val
	}
	return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val)
}

func main() {
	// 输入处理
	var input string
	fmt.Scanln(&input)
	targetSumStr := ""
	fmt.Scanln(&targetSumStr)
	targetSum, _ := strconv.Atoi(targetSumStr)

	values := strings.Split(input, ",")
	root, _ := buildTree(values)

	// 判断是否存在满足条件的路径
	if hasPathSum(root, targetSum) {
		fmt.Println("True")
	} else {
		fmt.Println("False")
	}
}

输入层序

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// 定义树节点结构
type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

// 根据层序遍历结果构建二叉树
func buildTree(levelOrder []string) *TreeNode {
	if len(levelOrder) == 0 || levelOrder[0] == "null" {
		return nil
	}
	root := &TreeNode{val: parseInt(levelOrder[0])}
	nodes := []*TreeNode{root}
	i := 1

	for len(nodes) > 0 && i < len(levelOrder) {
		current := nodes[0]
		nodes = nodes[1:]

		// 处理左子节点
		if i < len(levelOrder) && levelOrder[i] != "null" {
			current.left = &TreeNode{val: parseInt(levelOrder[i])}
			nodes = append(nodes, current.left)
		}
		i++

		// 处理右子节点
		if i < len(levelOrder) && levelOrder[i] != "null" {
			current.right = &TreeNode{val: parseInt(levelOrder[i])}
			nodes = append(nodes, current.right)
		}
		i++
	}
	return root
}

// 将字符串转换为整数，处理可能的 "null" 值
func parseInt(s string) int {
	if s == "null" {
		return 0 // 实际上这里返回什么并不重要，因为对应的节点不会被加入树中
	}
	val, _ := strconv.Atoi(s)
	return val
}

// 判断是否存在满足条件的路径
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.left == nil && root.right == nil {
		return targetSum == root.val
	}
	return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val)
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	levelOrderInput := scanner.Text()
	scanner.Scan()
	targetSumStr := scanner.Text()

	// 解析输入
	levelOrder := strings.Split(levelOrderInput, ",")
	targetSum, _ := strconv.Atoi(targetSumStr)

	// 构建二叉树
	root := buildTree(levelOrder)

	// 检查是否存在满足条件的路径
	if hasPathSum(root, targetSum) {
		fmt.Println("True")
	} else {
		fmt.Println("False")
	}
}