2026-10-20：统计二叉树中支配节点的数量。用go语言，给定一棵完全二叉树的根节点 root，树中每个节点都有一个值。 对于一个节点 x，考察

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。

大体步骤如下：

1. 1. 明确递归函数的职责
   定义一个递归函数，用来处理以某个节点为根的子树。它的核心任务是：返回这棵子树中所有节点值的最大值。同时，在递归过程中统计支配节点的数量。

2. 2. 处理空节点
   如果当前节点为空，说明已经越过了叶子节点。此时直接返回 0。
   题目中节点值都大于等于 1，所以把空子树的“最大值”设为 0 不会影响后续比较，也能让叶子节点自然地被判断为支配节点。

3. 3. 先递归处理左右子树
   对于当前节点，先分别递归处理它的左子树和右子树。
   左子树递归结束后会返回左子树中的最大值，右子树递归结束后会返回右子树中的最大值。
   因为先处理左右子树，再处理当前节点，所以整体是一个后序遍历式的深度优先搜索。

4. 4. 计算当前节点后代子树中的最大值
   将左子树返回的最大值和右子树返回的最大值进行比较，取较大的一个，记为 mx。
   此时 mx 表示当前节点的左右子树中所有节点值的最大值，不包含当前节点本身。

5. 5. 判断当前节点是否为支配节点
   比较当前节点的值和 mx。
   如果当前节点的值大于或等于 mx，说明当前节点值不小于它所有后代节点中的最大值。
   又因为子树最大值一定来自“当前节点本身”或“后代节点”，所以此时当前节点值就是整棵子树的最大值。
   因此当前节点满足“节点值等于子树中所有节点值的最大值”的条件，支配节点数量加一。
   如果当前节点值小于 mx，说明后代中存在比当前节点更大的值，当前节点不可能是子树最大值，不计数。

6. 6. 返回当前子树的整体最大值
   如果当前节点被判定为支配节点，也就是当前节点值大于或等于后代最大值，那么整棵子树的最大值就是当前节点值，于是把 mx 更新为当前节点值。
   如果当前节点不是支配节点，说明后代最大值 mx 已经大于当前节点值，整棵子树最大值仍然是 mx。
   最后把这个最大值返回给上一层递归。

7. 7. 主过程调用递归并得到答案
   从根节点开始调用递归函数。递归会自底向上处理每个节点，并在过程中不断累加支配节点数量。
   递归结束后，累加得到的数量就是整棵树中支配节点的总数，将其输出。

8. 8. 用示例说明执行过程
   示例完全二叉树按层序为：5、3、8、2、4、7、1。

• • 节点 2 是叶子，左右为空，后代最大值为 0，2 大于等于 0，计数加一，返回 2。

• • 节点 4 是叶子，后代最大值为 0，4 大于等于 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。

9. 时间复杂度
每个节点都会被递归访问一次，空节点也会产生常数次判断，因此总时间复杂度是 O(n)，其中 n 是树中节点数量。

10. 额外空间复杂度
算法主要使用递归调用栈。由于题目保证是完全二叉树，树的高度为 O(log n)，所以递归栈的最大深度也是 O(log n)。除递归栈外只使用了常数个变量。因此总额外空间复杂度是 O(log n)。

Go完整代码如下：

package main

 import"fmt"

 type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

 func countDominantNodes(root *TreeNode) (ans int) {
    // dfs(node) 返回 node 子树中的最大节点值
    var dfs func(*TreeNode)int
    dfs = func(node *TreeNode)int {
        if node == nil {
            return0
        }

         mx := maxInt(dfs(node.Left), dfs(node.Right))
        if node.Val >= mx {
            // node.Val 是 node 子树中的最大节点值
            ans++
            mx = node.Val
        }
        return mx
    }

     dfs(root)
    return
}

 func maxInt(a, b int)int {
    if a > b {
        return a
    }
    return b
}

 func main() {
    // 完全二叉树层序为：5, 3, 8, 2, 4, 7, 1
    root := &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-*-

 from typing import Optional

 class TreeNode:
    def __init__(self, val: int = 0,
                 left: Optional["TreeNode"] = None,
                 right: Optional["TreeNode"] = None):
        self.val = val
        self.left = left
        self.right = right

 def count_dominant_nodes(root: Optional[TreeNode]) -> int:
    ans = 0

     # dfs(node) 返回 node 子树中的最大节点值
    def dfs(node: Optional[TreeNode]) -> int:
        nonlocal ans
        if node is None:
            return0

         mx = max(dfs(node.left), dfs(node.right))
        if node.val >= mx:
            # node.val 是 node 子树中的最大节点值
            ans += 1
            mx = node.val
        return mx

     dfs(root)
    return ans

 if __name__ == "__main__":
    # 完全二叉树层序为：5, 3, 8, 2, 4, 7, 1
    root = TreeNode(
        5,
        left=TreeNode(
            3,
            left=TreeNode(2),
            right=TreeNode(4),
        ),
        right=TreeNode(
            8,
            left=TreeNode(7),
            right=TreeNode(1),
        ),
    )

     result = count_dominant_nodes(root)
    print(result)

C++完整代码如下：

  

  


 struct TreeNode {
    int Val;
    TreeNode *Left;
    TreeNode *Right;

     TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : Val(val), Left(left), Right(right) {}
};

 int countDominantNodes(TreeNode *root) {
    int ans = 0;

     // dfs(node) 返回 node 子树中的最大节点值
    // 用 std::function 或者 lambda 递归；这里用 auto 自递归 Lambda
    auto dfs = [&](auto &&self, TreeNode *node) -> int {
        if (node == nullptr) {
            return0;
        }

         int mx = std::max(self(self, node->Left), self(self, node->Right));
        if (node->Val >= mx) {
            // node->Val 是 node 子树中的最大节点值
            ++ans;
            mx = node->Val;
        }
        return mx;
    };

     dfs(dfs, root);
    return ans;
}

 int main() {
    // 完全二叉树层序为：5, 3, 8, 2, 4, 7, 1
    TreeNode *root = new TreeNode(
        5,
        new TreeNode(
            3,
            new TreeNode(2),
            new TreeNode(4)
            ),
        new TreeNode(
            8,
            new TreeNode(7),
            new TreeNode(1)
            )
        );

     int result = countDominantNodes(root);
    std::cout << result << std::endl;

     // 释放内存
    auto freeTree = [](auto &&self, TreeNode *node) -> void {
        if (node == nullptr) return;
        self(self, node->Left);
        self(self, node->Right);
        delete node;
    };
    freeTree(freeTree, root);

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。