965. Univalued Binary Tree

I like to read this solution as a small machine: keep the useful information, throw away the noise. For 965. Univalued Binary Tree, the solution in this repository is mainly a two pointers solution.

Guide

What?

The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:

What state are we keeping?
How do we move from one state to the next?
When do we know the answer is already determined?

For this file, the main tools are: two pointers, sliding window.

Guide

When?

Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.

The important function names to track are isUnivalTree, dfs.

Guide

Why?

The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.

The queue gives the solution a level-by-level or frontier-style traversal.
The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.

Guide

How?

Walk through the solution in this order:

Initialize the memory or helper structure.
Process candidates in the order the invariant expects.
Update the answer only when the current state is valid.
Return the value that represents the fully processed input.

The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.

Guide

Complexity

Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
Space: O(n) in the usual case for auxiliary containers or recursion

Guide

C++ Solution

Your submission

The accepted solution

solution.cpp

01/**
02A binary tree is univalued if every node in the tree has the same value.
03
04Return true if and only if the given tree is univalued.
05
06 
07
08Example 1:
09
10
11Input: [1,1,1,1,1,null,1]
12Output: true
13Example 2:
14
15
16Input: [2,2,2,5,2]
17Output: false
18 
19
20Note:
21
22The number of nodes in the given tree will be in the range [1, 100].
23Each node's value will be an integer in the range [0, 99].
24**/
25
26//Runtime: 4 ms, faster than 93.20% of C++ online submissions for Univalued Binary Tree.
27/**
28 * Definition for a binary tree node.
29 * struct TreeNode {
30 *     int val;
31 *     TreeNode *left;
32 *     TreeNode *right;
33 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
34 * };
35 */
36class Solution {
37public:
38    bool isUnivalTree(TreeNode* root) {
39        int unival = root->val;
40        TreeNode* cur = root;
41        queue<TreeNode*> queue;
42        queue.push(cur);
43        
44        while(!queue.empty()){
45            if(cur->val!=unival){
46                return false;
47            }
48            if(cur->left!=NULL)
49                queue.push(cur->left);
50            if(cur->right!=NULL)
51                queue.push(cur->right);
52            cur = queue.front();
53            queue.pop();
54        }
55        
56        return true;
57    }
58};
59
60/**
61Solution
62Approach 1: Depth-First Search
63Intuition and Algorithm
64
65Let's output all the values of the array. After, we can check that they are all equal.
66
67To output all the values of the array, we perform a depth-first search.
68//Java
69class Solution {
70    List<Integer> vals;
71    public boolean isUnivalTree(TreeNode root) {
72        vals = new ArrayList();
73        dfs(root);
74        for (int v: vals)
75            if (v != vals.get(0))
76                return false;
77        return true;
78    }
79
80    public void dfs(TreeNode node) {
81        if (node != null) {
82            vals.add(node.val);
83            dfs(node.left);
84            dfs(node.right);
85        }
86    }
87}
88
89Complexity Analysis
90
91Time Complexity: O(N), where N is the number of nodes in the given tree.
92
93Space Complexity: O(N). 
94
95Approach 2: Recursion
96Intuition and Algorithm
97
98A tree is univalued if both its children are univalued, plus the root node has the same value as the child nodes.
99
100We can write our function recursively. 
101left_correct will represent that the left child is correct: 
102ie., that it is univalued, and the root value is equal to the left child's value. 
103right_correct will represent the same thing for the right child. 
104We need both of these properties to be true.
105
106Complexity Analysis
107
108Time Complexity: O(N), where N is the number of nodes in the given tree.
109
110Space Complexity: O(H), where H is the height of the given tree. 
111
112//Runtime: 4 ms, faster than 93.20% of C++ online submissions for Univalued Binary Tree.
113
114class Solution {
115public:
116    bool isUnivalTree(TreeNode* root) {
117        bool left_correct = (root->left==NULL || 
118            (root->val == root->left->val && isUnivalTree(root->left)));
119        bool right_correct = (root->right==NULL ||
120            (root->val == root->right->val && isUnivalTree(root->right)));
121        return left_correct && right_correct;
122    }
123};
124**/

Cost

Complexity

Time

O(n) to O(n log n), depending on the dominant loop or data structure operation

Dominated by the main traversal, recursion, or data-structure operations in the code.

Space

O(n) in the usual case for auxiliary containers or recursion

Auxiliary state plus the answer structure where the problem requires one.