目录题目思路Code题目天命人深入盘丝洞洞内布满了蜘蛛精设下的迷阵。整座洞穴呈二叉树结构每个结点是一间石室石室中藏有灵气结晶灵气值为整数可正可负0 视为非负。天命人从根石室出发寻找通往叶子石室的路径收集灵气。但盘丝洞有毒瘴禁制路径上不允许出现连续两个或以上灵气值为负的石室。叶子石室定义为左右子结点均为空的结点。请实现一个函数在一遍遍历中同时计算以下三个指标第1点合法路径的最大灵气和。第2点是否存在合法路径和大于等于给定阈值 target。第3点合法路径数量。合法路径必须从根结点出发并到达叶子结点且路径中不能出现连续两个负数结点。输入描述输入包括二叉树根结点 root 和整数阈值 target。公开页面以函数题形式描述二叉树可按层序数组表示空子结点记为 null。例如root [5,4,-3,null,null,2,7]target 8输出描述输出三个指标maxSum, hasPathAtLeastTarget, countmaxSum所有合法根到叶路径中的最大灵气和。hasPathAtLeastTarget是否存在合法路径和大于等于 target。count合法根到叶路径数量。如果不存在合法路径count 为 0最大灵气和按实现约定可返回极小值或特殊值需与函数接口说明保持一致。样例 1输入root [5,4,-3,null,null,2,7]target 8输出9,true,3说明合法路径为5 - 4路径和为 95 - -3 - 2路径和为 45 - -3 - 7路径和为 9合法路径数量为 3最大路径和为 9存在路径和大于等于 target 8。样例 2连续负数剪枝输入root [1,-2,3,-4,null,null,5]target 6输出9,true,1说明路径 1 - -2 - -4 出现连续两个负数非法路径 1 - 3 - 5 合法路径和为 9。思路DFS 深度遍历先按层序数组构建二叉树null 表示空节点。然后从根节点开始深度优先搜索递归参数带上当前路径和以及上一节点是否为负数。访问当前节点时如果上一节点和当前节点都是负数说明路径已经违反规则直接剪枝。只有走到叶子节点时才把当前路径计为一条完整合法路径并更新合法路径数量、最大路径和以及是否存在路径和不小于 target。整个过程每个节点最多访问一次。Codeimport re root_line input().strip() # 读取层序数组和 targetnull 位置表示不存在节点。 target_line input().strip() # DFS 状态包含数组下标、当前路径和以及上一节点是否为负。 tokens re.search(r\[(.*)\], root_line).group(1).split(,) # 当前节点和上一节点连续为负时路径非法直接剪枝。 arr [None if x.strip() null else int(x.strip()) for x in tokens] target int(re.search(r-?\d, target_line).group()) max_sum -10 ** 18 count 0 has_target False def dfs(i, cur_sum, prev_neg): global max_sum, count, has_target if i len(arr) or arr[i] is None: return val arr[i] cur_neg val 0 # 连续两个负数时当前路径非法。 if prev_neg and cur_neg: return new_sum cur_sum val left, right 2 * i 1, 2 * i 2 is_leaf (left len(arr) or arr[left] is None) and (right len(arr) or arr[right] is None) if is_leaf: count 1 max_sum max(max_sum, new_sum) has_target has_target or new_sum target return dfs(left, new_sum, cur_neg) dfs(right, new_sum, cur_neg) dfs(0, 0, False) # 按 maxSum,hasPathAtLeastTarget,count 的格式输出。 print(f{max_sum},{str(has_target).lower()},{count})JSconst fs require(fs); // 读取层序数组和 targetnull 位置表示不存在节点。 const lines fs.readFileSync(0, utf8).trim().split(/\n/); const inside lines[0].slice(lines[0].indexOf([) 1, lines[0].lastIndexOf(])); const arr inside.split(,).map(s { s s.trim(); return s null ? null : Number(s); }); const target Number(lines[1].match(/-?\d/)[0]); // 到达叶子后才更新路径数量、最大路径和以及 target 判断。 let maxSum -Infinity; // DFS 状态包含数组下标、当前路径和以及上一节点是否为负。 let count 0; let hasTarget false; function dfs(i, sum, prevNeg) { if (i arr.length || arr[i] null) return; const curNeg arr[i] 0; // 连续两个负数时剪枝。 if (prevNeg curNeg) return; const newSum sum arr[i]; const left 2 * i 1, right 2 * i 2; const leaf (left arr.length || arr[left] null) (right arr.length || arr[right] null); if (leaf) { count; maxSum Math.max(maxSum, newSum); if (newSum target) hasTarget true; return; } dfs(left, newSum, curNeg); dfs(right, newSum, curNeg); } dfs(0, 0, false); // 按 maxSum,hasPathAtLeastTarget,count 的格式输出。 console.log(${maxSum},${hasTarget},${count});【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。