LeetCode 1145. 二叉树着色游戏

Categories:

题目描述
思路分析
1. 解法一：统计三块区域大小（推荐）
相似题目

题目描述

✅ 1145. 二叉树着色游戏

思路分析

解法一：统计三块区域大小（推荐）

核心思路：

先找到节点 x 的左子树大小 L 和右子树大小 R。

剩余区域大小 P = n - L - R - 1。

第二个玩家若能占据任意一块大于 n/2 的区域即可获胜。

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数。

空间复杂度：O(h)，其中 h 为树高。

class Solution {
    private int leftSize = 0;
    private int rightSize = 0;

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        count(root, x);
        int parent = n - leftSize - rightSize - 1;
        int max = Math.max(parent, Math.max(leftSize, rightSize));
        return max > n / 2;
    }

    private int count(TreeNode node, int x) {
        if (node == null) {
            return 0;
        }
        int left = count(node.left, x);
        int right = count(node.right, x);
        if (node.val == x) {
            leftSize = left;
            rightSize = right;
        }
        return left + right + 1;
    }
}

func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
    leftSize, rightSize := 0, 0

    var count func(node *TreeNode) int
    count = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := count(node.Left)
        right := count(node.Right)
        if node.Val == x {
            leftSize = left
            rightSize = right
        }
        return left + right + 1
    }

    count(root)
    parent := n - leftSize - rightSize - 1
    maxPart := parent
    if leftSize > maxPart {
        maxPart = leftSize
    }
    if rightSize > maxPart {
        maxPart = rightSize
    }
    return maxPart > n/2
}

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	DFS
124. 二叉树中的最大路径和	困难	DFS
1110. 删点成林	中等	DFS
1145. 二叉树着色游戏	中等	子树大小
968. 监控二叉树	困难	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/60448789