安徽城乡建设 厅网站,电子商务网站建设需要哪些步骤,产品展示网站方案,动态的网站大概多少钱1. 题目描述
题目链接
2. 解题思路
首先看一下题目的“核心”#xff0c;什么是好节点#xff1a;从根到该节点 X 所经过的节点中#xff0c;没有任何节点的值大于 X 的值。也就是说#xff0c;我们只要知道了从根节点到该节点的所有的值#xff0c;就可以判断该节点是…1. 题目描述
题目链接
2. 解题思路
首先看一下题目的“核心”什么是好节点从根到该节点 X 所经过的节点中没有任何节点的值大于 X 的值。也就是说我们只要知道了从根节点到该节点的所有的值就可以判断该节点是不是好节点了。从根节点到x节点很容易想到先序遍历深度优先先序遍历访问的顺序恰好是根节点到该节点的路径顺序我们可以在递归遍历的过程中记录路径上的最大值然后比较当前节点的值和路径上的最大值来确定是否为好节点。
如果当前节点的值大于或等于路径上的最大值则将其计为好节点并更新路径上的最大值 否则我们不将其计为好节点。
再递归遍历左、右子树时我们分别传递更新后的路径上的最大值这样可以确保路径上的最大值的更新在递归遍历中被正确传递和更新。
3. 代码
public class GoodNodes {/*给你一棵根为 root 的二叉树请你返回二叉树中好节点的数目。「好节点」X 定义为从根到该节点 X 所经过的节点中没有任何节点的值大于 X 的值。*/private int goodCount 0; // 将好节点计数设置为类的成员变量public int goodNodes(TreeNode root) {countGoodNodes(root, Integer.MIN_VALUE); // 从根节点开始计算好节点return goodCount; // 返回累计的好节点数量}private void countGoodNodes(TreeNode node, int maxSoFar) {if (node null) return; // 如果当前节点为空则返回if (node.val maxSoFar) { // 如果当前节点的值大于或等于路径上的最大值goodCount; // 将当前节点计为好节点maxSoFar node.val; // 更新路径上的最大值为当前节点的值}// 递归遍历左子树和右子树分别传递更新后的路径上的最大值countGoodNodes(node.left, maxSoFar);countGoodNodes(node.right, maxSoFar);}/*由于先序遍历访问的顺序恰好是根节点到该节点的路径顺序我们可以在递归遍历的过程中记录路径上的最大值然后比较当前节点的值和路径上的最大值来确定是否为好节点。如果当前节点的值大于或等于路径上的最大值则将其计为好节点并更新路径上的最大值否则我们不将其计为好节点。在递归遍历左右子树时我们分别传递更新后的路径上的最大值这样可以确保路径上的最大值的更新在递归遍历中被正确传递和更新。因此通过修改先序遍历的代码来记录路径上的最大值并比较节点的值和路径上的最大值我们可以计算出好节点的数量。* */
}
