Count Univalue Subtrees

Question

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

Solution

第一次寫的時候，寫了一個錯誤的寫法，但也只剩 6 個 test case 沒過。那時的想法是，寫個 recursion 去判斷，如果 root.val == root.left.val && root.val == root.right.val，就等於是 uni-value tree。但這樣的思路很明顯是不對的，因為這樣寫等於只檢查當前跟下面那層，但並沒有確認到整棵樹。

後來換了個寫法就 accept 了。我等於用了兩層 recursion。概念是，我先等左子樹跟右子樹判斷完，如果兩邊都回給我 true，那就表示那兩邊都是 uni-value subtree，接著再判斷 root 的值跟左右子樹是否相同。

    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return 1;
        }

        boolean left = helper(root.left);
        boolean right = helper(root.right);

        if (root.left != null && root.right == null) {
            if (left && root.val == root.left.val) {
                return 1 + countUnivalSubtrees(root.left);
            } else {
                return countUnivalSubtrees(root.left);
            }
        } else if (root.left == null && root.right != null) {
            if (right && root.val == root.right.val) {
                return 1 + countUnivalSubtrees(root.right);
            } else {
                return countUnivalSubtrees(root.right);
            }
        }

        return (root.val == root.left.val && root.val == root.right.val && left && right) ? 1 + countUnivalSubtrees(root.left) + countUnivalSubtrees(root.right) : countUnivalSubtrees(root.left) + countUnivalSubtrees(root.right);
    }

    public boolean helper(TreeNode t) {
        if (t == null) {
            return false;
        } else if (t.left == null && t.right == null) {
            return true;
        }

        if (t.left != null && t.right == null) {
            if (t.val != t.left.val) {
                return false;
            } else {
                return helper(t.left);
            }
        } else if (t.right != null && t.left == null) {
            if (t.val != t.right.val) {
                return false;
            } else {
                return helper(t.right);
            }
        }

        if (t.val != t.left.val || t.val != t.right.val) {
            return false;
        } 

        return helper(t.left) && helper(t.right);
    }

參考了解答，也是類似思路，只是寫的比較 concise。

    public int countUnivalSubtrees(TreeNode root) {
        int[] count = new int[1];
        helper(root, count);
        return count[0];
    }

    private boolean helper(TreeNode node, int[] count) {
        if (node == null) {
            return true;
        }
        boolean left = helper(node.left, count);
        boolean right = helper(node.right, count);
        if (left && right) {
            if (node.left != null && node.val != node.left.val) {
                return false;
            }
            if (node.right != null && node.val != node.right.val) {
                return false;
            }
            count[0]++;
            return true;
        }
        return false;
    }