2026-10-20统计二叉树中支配节点的数量。用go语言给定一棵完全二叉树的根节点 root树中每个节点都有一个值。对于一个节点 x考察由 x 本身以及它的全部后代节点组成的子树。如果 x 的值恰好等于这个子树中所有节点值的最大值那么就称 x 是一个支配节点。完全二叉树是指除了最后一层之外其余每一层都被节点填满最后一层的节点则按照从左到右的顺序尽量靠左排列。现在需要统计并返回这棵树中支配节点的总数。树中的节点数量在范围 [1, 100000] 内。1 Node.val 1000000000。保证给定的树是一棵完全二叉树。输入 root [5,3,8,2,4,7,1]。输出 5。解释值为 2、4、7 和 1 的叶节点都是支配节点。值为 8 的节点是支配节点因为它的值是其子树 [8, 7, 1] 中的最大值。因此答案为 5。题目来自力扣3997。大体步骤如下明确递归函数的职责定义一个递归函数用来处理以某个节点为根的子树。它的核心任务是返回这棵子树中所有节点值的最大值。同时在递归过程中统计支配节点的数量。处理空节点如果当前节点为空说明已经越过了叶子节点。此时直接返回 0。题目中节点值都大于等于 1所以把空子树的“最大值”设为 0 不会影响后续比较也能让叶子节点自然地被判断为支配节点。先递归处理左右子树对于当前节点先分别递归处理它的左子树和右子树。左子树递归结束后会返回左子树中的最大值右子树递归结束后会返回右子树中的最大值。因为先处理左右子树再处理当前节点所以整体是一个后序遍历式的深度优先搜索。计算当前节点后代子树中的最大值将左子树返回的最大值和右子树返回的最大值进行比较取较大的一个记为 mx。此时 mx 表示当前节点的左右子树中所有节点值的最大值不包含当前节点本身。判断当前节点是否为支配节点比较当前节点的值和 mx。如果当前节点的值大于或等于 mx说明当前节点值不小于它所有后代节点中的最大值。又因为子树最大值一定来自“当前节点本身”或“后代节点”所以此时当前节点值就是整棵子树的最大值。因此当前节点满足“节点值等于子树中所有节点值的最大值”的条件支配节点数量加一。如果当前节点值小于 mx说明后代中存在比当前节点更大的值当前节点不可能是子树最大值不计数。返回当前子树的整体最大值如果当前节点被判定为支配节点也就是当前节点值大于或等于后代最大值那么整棵子树的最大值就是当前节点值于是把 mx 更新为当前节点值。如果当前节点不是支配节点说明后代最大值 mx 已经大于当前节点值整棵子树最大值仍然是 mx。最后把这个最大值返回给上一层递归。主过程调用递归并得到答案从根节点开始调用递归函数。递归会自底向上处理每个节点并在过程中不断累加支配节点数量。递归结束后累加得到的数量就是整棵树中支配节点的总数将其输出。用示例说明执行过程示例完全二叉树按层序为5、3、8、2、4、7、1。节点 2 是叶子左右为空后代最大值为 02 大于等于 0计数加一返回 2。节点 4 是叶子后代最大值为 04 大于等于 0计数加一返回 4。节点 3 的左子树最大值为 2右子树最大值为 4后代最大值为 4。因为 3 小于 4所以节点 3 不是支配节点返回 4。节点 7 是叶子计数加一返回 7。节点 1 是叶子计数加一返回 1。节点 8 的左子树最大值为 7右子树最大值为 1后代最大值为 7。因为 8 大于等于 7所以节点 8 是支配节点计数加一返回 8。根节点 5 的左子树最大值为 4右子树最大值为 8后代最大值为 8。因为 5 小于 8所以根节点 5 不是支配节点返回 8。最终被计数的节点是 2、4、7、1、8共 5 个输出 5。时间复杂度每个节点都会被递归访问一次空节点也会产生常数次判断因此总时间复杂度是 O(n)其中 n 是树中节点数量。额外空间复杂度算法主要使用递归调用栈。由于题目保证是完全二叉树树的高度为 O(log n)所以递归栈的最大深度也是 O(log n)。除递归栈外只使用了常数个变量。因此总额外空间复杂度是 O(log n)。Go完整代码如下packagemainimportfmttypeTreeNodestruct{ValintLeft*TreeNode Right*TreeNode}funccountDominantNodes(root*TreeNode)(ansint){// dfs(node) 返回 node 子树中的最大节点值vardfsfunc(*TreeNode)intdfsfunc(node*TreeNode)int{ifnodenil{return0}mx:maxInt(dfs(node.Left),dfs(node.Right))ifnode.Valmx{// node.Val 是 node 子树中的最大节点值ansmxnode.Val}returnmx}dfs(root)return}funcmaxInt(a,bint)int{ifab{returna}returnb}funcmain(){// 完全二叉树层序为5, 3, 8, 2, 4, 7, 1root:TreeNode{Val:5,Left:TreeNode{Val:3,Left:TreeNode{Val:2,},Right:TreeNode{Val:4,},},Right:TreeNode{Val:8,Left:TreeNode{Val:7,},Right:TreeNode{Val:1,},},}result:countDominantNodes(root)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportOptionalclassTreeNode:def__init__(self,val:int0,left:Optional[TreeNode]None,right:Optional[TreeNode]None):self.valval self.leftleft self.rightrightdefcount_dominant_nodes(root:Optional[TreeNode])-int:ans0# dfs(node) 返回 node 子树中的最大节点值defdfs(node:Optional[TreeNode])-int:nonlocalansifnodeisNone:return0mxmax(dfs(node.left),dfs(node.right))ifnode.valmx:# node.val 是 node 子树中的最大节点值ans1mxnode.valreturnmx dfs(root)returnansif__name____main__:# 完全二叉树层序为5, 3, 8, 2, 4, 7, 1rootTreeNode(5,leftTreeNode(3,leftTreeNode(2),rightTreeNode(4),),rightTreeNode(8,leftTreeNode(7),rightTreeNode(1),),)resultcount_dominant_nodes(root)print(result)C完整代码如下#includeiostream#includealgorithmstructTreeNode{intVal;TreeNode*Left;TreeNode*Right;TreeNode(intval0,TreeNode*leftnullptr,TreeNode*rightnullptr):Val(val),Left(left),Right(right){}};intcountDominantNodes(TreeNode*root){intans0;// dfs(node) 返回 node 子树中的最大节点值// 用 std::function 或者 lambda 递归这里用 auto 自递归 Lambdaautodfs[](autoself,TreeNode*node)-int{if(nodenullptr){return0;}intmxstd::max(self(self,node-Left),self(self,node-Right));if(node-Valmx){// node-Val 是 node 子树中的最大节点值ans;mxnode-Val;}returnmx;};dfs(dfs,root);returnans;}intmain(){// 完全二叉树层序为5, 3, 8, 2, 4, 7, 1TreeNode*rootnewTreeNode(5,newTreeNode(3,newTreeNode(2),newTreeNode(4)),newTreeNode(8,newTreeNode(7),newTreeNode(1)));intresultcountDominantNodes(root);std::coutresultstd::endl;// 释放内存autofreeTree[](autoself,TreeNode*node)-void{if(nodenullptr)return;self(self,node-Left);self(self,node-Right);deletenode;};freeTree(freeTree,root);return0;}