算法练习 Leetcode 力扣 1145. Binary Tree Coloring Game 解法

feellikelearning March 22, 2020 0 Comments

这题描述巨长无比，可以当一篇阅读理解来做了，看完也不是很容易就能想到是属于哪类的题目，图也画的非常有迷惑性，蓝色应该画在1位置能多占一个。热爱做脑筋急转弯的同学可以挑战一下，没时间的同学就直接记住结论就好，蓝色的可能选择其实只有3个：红色的左边，右边，和上面，分别切断和占领左右上三部分，然后看看每部分能不能超过一半就好。有了这个思路，用DFS跑一次就行，时间是O(n)，没有explicit extra space，但算上DFS递归占用stack也是O(n)

Python 实现

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        xnode = self.find(root, x)
        (xcount, lcount, rcount) = self.tree_stats(xnode)
        half = n / 2
        if lcount > half or rcount > half or n - xcount > half:
            return True
        return False
        
    
    def find(self, root, x):
        if root is None:
            return None
        if root.val == x:
            return root
        l = self.find(root.left, x)
        if l is not None:
            return l
        else:
            return self.find(root.right, x)
        
    def tree_stats(self, root):
        if root is None:
            return (0, 0, 0)
        l = self.tree_stats(root.left)
        r = self.tree_stats(root.right)
        return (l[0] + r[0] + 1, l[0], r[0])

还有一种写法，可以把查找和算子树节点个数合并成一个DFS，trick就是用一个container参数记录当找到x时，他的左中上能控制的节点树，其他部分就是正常的DFS。能缩短代码。

Python 实现

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        ans = []
        self.tree_stats(root, x, n, ans)
        return ans[0] > n / 2
             
    def tree_stats(self, root, x, n, ans):
        if root is None:
            return 0
        l = self.tree_stats(root.left, x, n, ans)
        r = self.tree_stats(root.right, x, n, ans)
        cnt = l + r + 1
        if root.val == x:
            ans.append(max(l, r, n - cnt))
        return cnt

Java 实现

class Solution {
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        int [] ans = new int[1];
        nodes(root, n, x, ans);
        return ans[0] > n / 2;
    }
    
    public int nodes(TreeNode root, int n, int x, int[] ans) {
        if (root == null) {
            return 0;
        }
        int l = nodes(root.left, n, x, ans);
        int r = nodes(root.right, n, x, ans);
        int cnt = l + r + 1;
        if (root.val == x) {
            ans[0] = Math.max(Math.max(l, r), n - cnt);
        }
        return cnt;
    }
}

Scala 实现

object Solution {
    def btreeGameWinningMove(root: TreeNode, n: Int, x: Int): Boolean = {
        val ans: Array[Int] = new Array(1)
        nodes(root, n, x, ans)
        return ans(0) > n / 2
    }
    
    def nodes(root: TreeNode, n: Int, x: Int, ans: Array[Int]): Int = {
        if (root == null) {
            0
        } else {
            val l: Int = nodes(root.left, n, x, ans)
            val r: Int = nodes(root.right, n, x, ans)
            val cnt: Int = l + r + 1
            if (root.value == x) {
                ans(0) = scala.math.max(scala.math.max(l, r), n - cnt) 
            }
            cnt
        }
    }
}

Scala和Java基本一样，就是注意没有return statement，最后一个表达式就是return值。还有定义函数记得要加 =