993. Cousins in Binary Tree
1. Description
Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.
Two nodes of a binary tree are cousins if they have the same depth with different parents.
Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.
2. Example
Example 1:
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Example 2:
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Example 3:
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false
3. Constraints
- The number of nodes in the tree is in the range [2, 100].
- 1 <= Node.val <= 100
- Each node has a unique value.
- x != y
- x and y are exist in the tree.
4. Solutions
Depth-First Search
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
bool isCousins(TreeNode *root, int x, int y) {
traverse(root, x, y, 0);
return (x_parent != y_parent) && (x_depth_ == y_depth_);
}
void traverse(TreeNode *root, int x, int y, int depth) {
if (root != nullptr) {
if (root->left != nullptr && root->left->val == x ||
root->right != nullptr && root->right->val == x) {
x_depth_ = depth + 1;
x_parent = root;
} else if (
root->left != nullptr && root->left->val == y ||
root->right != nullptr && root->right->val == y) {
y_depth_ = depth + 1;
y_parent = root;
}
traverse(root->left, x, y, depth + 1);
traverse(root->right, x, y, depth + 1);
}
}
private:
int x_depth_ = 0;
TreeNode *x_parent = nullptr;
int y_depth_ = 0;
TreeNode *y_parent = nullptr;
};