华为秋季机试三道编程题（2021-09-08）

通知：华为、阿里最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在微信公众号【TechGuide】了，私信公众号回复【华为】或者【阿里】即可获得最实时、最详细的笔试题解啦！

第一道：最优节点（100%） 题目描述

给出一颗二叉树，每个节点有一个编号和一个值，该值可能为负数，请你找出一个最优节点(除根节点外)，使得在该节点将树分成两棵树后(原来的树移除这个节点及其子节点，新的树以该节点为根节点)，分成的两棵树各节点的和之间的差绝对值最大。

请输出该节点编号，如有多个相同的差，输出编号最小的节点。

输入描述 4 4 9 -7 -8 0 1 0 3 1 2 第一行，四个节点，编号0-3，范围为1-10000 第二行，节点0-3的权值 第三行到第五行，表示二叉树各节点间的父子关系 0 1 //节点0的左节点是1 0 3 //节点0的右节点是3 1 2 //节点1的左节点是2 注意:左节点永远出现在右节点之前

4
4 9 -7 -8
0 1
0 3
1 2

输出描述

节点编号，示例中编号为3的节点是最优节点

3

参考代码

暴力dfs, 求每一个结点以及其所有子结点的和就可以, 注意需要使用long long

// 关注TechGuide！ 大厂笔经面经闪电速递！

第二道： 梅花桩（100%） 题目描述

有一个 M*N 的梅花桩阵，每个桩都有允许跳跃的最大步数，用户从0,0的位置开始跳跃，允许向右和向下两个方向跳跃，求最少要跳跃多少次能到达M-1，N-1的位置。无法到达目的地时返回-1。

M