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
.
Solution: Preorder traversal
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua, running time 8 ms, 11.5 MB class Solution { public: bool isCousins(TreeNode* root, int x, int y) { preorder(root, x, y, nullptr, 0); return px_ != py_ && dx_ == dy_; } private: TreeNode* px_; TreeNode* py_; int dx_; int dy_; void preorder(TreeNode* root, int x, int y, TreeNode* p, int d) { if (!root) return; if (root->val == x) { px_ = p; dx_ = d; } if (root->val == y) { py_ = p; dy_ = d; } preorder(root->left, x, y, root, d + 1); preorder(root->right, x, y, root, d + 1); } }; |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua, running time: 40 ms, 12.4 MB class Solution: def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool': self.px, self.dx = None, -1 self.py, self.dy = None, -2 def preorder(root, parent, d): if not root: return if root.val == x: self.px, self.dx = parent, d if root.val == y: self.py, self.dy = parent, d preorder(root.left, root, d + 1) preorder(root.right, root, d + 1) preorder(root, None, 0) return self.dx == self.dy and self.px != self.py |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment