20230920 网宿科技笔试

100/30 第二题的构建二叉树，按照题意构建了二叉树，不知道为什么只过了30，后面有一个本地测试样例没过，修改了一下，考虑了负数节点，又变成9%，果断选择跑路.

我手撕树的题目做的太少了，很多时候只过了样例，没办法AC，欢迎各方大佬指点

package main

import (
	"fmt"
	"math"
	"sort"
)

type Node struct {
	Val   int
	No    int
	Left  *Node
	Right *Node
}

func buildTree(tree []Node) *Node {
	if len(tree) == 0 {
		return nil
	}
	root := &Node{Val: tree[0].Val, No: index}
	index++
	for i := range tree {
		if tree[i].No == root.No {
			if root.Left == nil {
				root.Left = buildTree(tree[1:])
			} else if root.Right == nil {
				root.Right = buildTree(tree[2:])
			}
		}
	}
	return root
}

var index int

func main() {
	var n int
	fmt.Scanln(&n)
	tree := make([]Node, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&tree[i].Val)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&tree[i].No)
	}
	sort.Slice(tree, func(i, j int) bool {
		return tree[i].No < tree[j].No
	})
	index = 1
	root := buildTree(tree)
	// PrintList(root)
	fmt.Println(search(root))
}

func search(root *Node) int {
	if root == nil {
		return math.MinInt
	}
	left := search(root.Left)
	right := search(root.Right)
	// fmt.Println(left,right)
	if left+root.Val < left || right+root.Val < right {
		return max(left, max(root.Val, right))
	}

	return left + right + root.Val
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}