Question
In a binary tree, the root node is at depth 0
, and children of each depth k
node are at depth k+1
.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root
of a binary tree with unique values, and the values x
and y
of two different nodes in the tree.
Return true
if and only if the nodes corresponding to the values x
and y
are cousins.
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
Note:
- The number of nodes in the tree will be between
2
and100
. - Each node has a unique integer value from
1
to100
.
Difficulty:Easy
Category:
Analyze
Solution
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
if ((level(root, x, 1) == level(root, y, 1)) && !(isSibling(root, x, y))) return true;
return false;
}
private:
bool isSibling(TreeNode* root, int a, int b) {
if (!root) return false;
if (root->left && root->right) {
if ((root->left->val == a && root->right->val == b) || (root->right->val == a && root->left->val == b)) {
return true;
}
}
return isSibling(root->left, a, b) || isSibling(root->right, a, b);
}
int level(TreeNode* root, int target, int lev) {
if (!root) return 0;
if (root->val == target) return lev;
int l = level(root->left, target, lev + 1);
if (l != 0) return l;
return level(root->right, target, lev + 1);
}
};