LeetCode 965 - Univalued Binary Tree

https://leetcode.com/problems/univalued-binary-tree/

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: [2,2,2,5,2]
Output: false

Note:

1. The number of nodes in the given tree will be in the range [1, 100].
2. Each node's value will be an integer in the range [0, 99]

https://leetcode.com/articles/univalued-binary-tree/
https://leetcode.com/problems/univalued-binary-tree/discuss/211190/JavaC%2B%2BPython-Straight-Forward

A tree is univalued if both its children are univalued, plus the root node has the same value as the child nodes.

We can write our function recursively. left_correct will represent that the left child is correct: ie., that it is univalued, and the root value is equal to the left child's value. right_correct will represent the same thing for the right child. We need both of these properties to be true.

  public boolean isUnivalTree(TreeNode root) {

    boolean left_correct = (root.left == null || (root.val == root.left.val && isUnivalTree(root.left)));

    boolean right_correct = (root.right == null || (root.val == root.right.val && isUnivalTree(root.right)));

    return left_correct && right_correct;

  }

https://leetcode.com/problems/univalued-binary-tree/discuss/211397/Java-9-and-4-liners-Iterative-and-recursive-versions.

Iterative version - BFS.

Analysis: Time & space: O(n).

    public boolean isUnivalTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n.val != root.val) { return false; }
            if (n.left != null) { q.offer(n.left); }        
            if (n.right != null) { q.offer(n.right); }        
        }
        return true;
    }

Recursive version - DFS.

Analysis: Time & space: O(n).

    public boolean isUnivalTree(TreeNode root) {
        return dfs(root, root.val);
    }
    private boolean dfs(TreeNode n, int v) {
        if (n == null) { return true; }
        if (n.val != v) { return false; }
        return dfs(n.left, v) && dfs(n.right, v);
    }    

Q & A
Q:
What if the root is null?

A:
We can add the following statement as the first line in isUnivalTree(TreeNode) for both method 1 & 2:

if (root == null) return true;

In fact, the problem description states "The number of nodes in the given tree will be in the range [1, 100].", which implies root != null.

https://leetcode.com/problems/univalued-binary-tree/discuss/211191/C%2B%2BJava-one-liner

boolean dfs(TreeNode r, int v) {
    return r == null || (r.val == v && dfs(r.left, v) && dfs(r.right, v));
}
public boolean isUnivalTree(TreeNode r) { return dfs(r, r.val); }

  List<Integer> vals;

  public boolean isUnivalTree(TreeNode root) {

    vals = new ArrayList();

    dfs(root);

    for (int v : vals)

      if (v != vals.get(0))

        return false;

    return true;

  }

  public void dfs(TreeNode node) {

    if (node != null) {

      vals.add(node.val);

      dfs(node.left);

      dfs(node.right);

    }

  }