算法練習 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值。還有定義函數記得要加 =