这题比较有意思, 拿来分享一下:
在二叉树中, 根节点在深度0处, 并且每个深度k节点的子节点在深度k + 1处. 如果二元树的两个节点具有相同的深度但具有不同的父节点, 则它们是堂/表兄弟. 我们给出了具有唯一值的二叉树的根, 以及树中两个不同节点的值x和y.
当且仅当对应于值x和y的节点是同类时, 才返回true.
例如:
1 2 3
2和3的父母是同一个, 所以不是表兄弟(妹)
1 2 3 4 5
4和5是, 因为来自不同的父母, 并且所以树的高度是一样的.
深度优先+递归
二叉树(或者图)的一些算法大多数都可以用深度优先DFS来实现, 这题也不例外. 深度优先可以用递归来实现较简单(当然也可以自己写迭代来操作堆栈)
我们可以用一次深度优先DFS来遍历所有节点, 并在过程中记录树结点的深度和父母. 需要用两个哈希表.
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 28 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isCousins(TreeNode* root, int x, int y) { dfs(root, NULL, 0); return (depth[x] == depth[y]) && (parent[x] != parent[y]); } void dfs(TreeNode* root, TreeNode* p, int d) { if (root == NULL) return; depth[root->val] = d; // 记录深度 parent[root->val] = p; // 记录父母 dfs(root->left, root, d + 1); dfs(root->right, root, d + 1); } private: unordered_map<int, int> depth; unordered_map<int, TreeNode*> parent; }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isCousins(TreeNode* root, int x, int y) { dfs(root, NULL, 0); return (depth[x] == depth[y]) && (parent[x] != parent[y]); } void dfs(TreeNode* root, TreeNode* p, int d) { if (root == NULL) return; depth[root->val] = d; // 记录深度 parent[root->val] = p; // 记录父母 dfs(root->left, root, d + 1); dfs(root->right, root, d + 1); } private: unordered_map<int, int> depth; unordered_map<int, TreeNode*> parent; };
然后再判断两个节点的父母和高度即可. 时间复杂度是O(N), 空间复杂度也是O(N). N是树的节点个数.
上面的算法我们还可以用稍微不同的实现. 让这个DFS函数同时返回树节点的深度和父节点.
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 28 29 30 31 32 33 34 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCousins(TreeNode* root, int x, int y) { pair<int, TreeNode*> a = dfs(root, x, 0, nullptr); pair<int, TreeNode*> b = dfs(root, y, 0, nullptr); return (a.first == b.first) && (a.second != b.second); } private: pair<int, TreeNode*> dfs(TreeNode* root, int val, int depth, TreeNode* parent) { // 如果找不到该节点, 就返回特殊值 if (root == nullptr) { return {0, nullptr}; } if (root->val == val) { return {depth, parent}; } auto a = dfs(root->left, val, depth + 1, root); if (a.first != 0) return a; auto b = dfs(root->right, val, depth + 1, root); return b; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCousins(TreeNode* root, int x, int y) { pair<int, TreeNode*> a = dfs(root, x, 0, nullptr); pair<int, TreeNode*> b = dfs(root, y, 0, nullptr); return (a.first == b.first) && (a.second != b.second); } private: pair<int, TreeNode*> dfs(TreeNode* root, int val, int depth, TreeNode* parent) { // 如果找不到该节点, 就返回特殊值 if (root == nullptr) { return {0, nullptr}; } if (root->val == val) { return {depth, parent}; } auto a = dfs(root->left, val, depth + 1, root); if (a.first != 0) return a; auto b = dfs(root->right, val, depth + 1, root); return b; } };
如果内存要求比较严格, 我们可以用4次深度优先来完成这个任务. 获取深度和获取父母需要各检查2次.
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isCousins(TreeNode* root, int x, int y) { TreeNode* leftParent = findParent(root, nullptr, x); TreeNode* rightParent = findParent(root, nullptr, y); if (leftParent == rightParent) return false; int dx = depth(root, 0, x); int dy = depth(root, 0, y); return dx == dy; } private: // 得到节点 v 的深度 int depth(TreeNode* root, int curDepth, int v) { if (root == nullptr) return 0; if (root->val == v) { return curDepth; } int x = depth(root->left, curDepth + 1, v); if (x > 0) return x; return depth(root->right, curDepth + 1, v); } // 得到节点 v 的父母 TreeNode* findParent(TreeNode* root, TreeNode* parent, int v) { if (root == nullptr) return nullptr; if (root->val == v) return parent; TreeNode* left = findParent(root->left, root, v); if (left != nullptr) return left; return findParent(root->right, root, v); } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isCousins(TreeNode* root, int x, int y) { TreeNode* leftParent = findParent(root, nullptr, x); TreeNode* rightParent = findParent(root, nullptr, y); if (leftParent == rightParent) return false; int dx = depth(root, 0, x); int dy = depth(root, 0, y); return dx == dy; } private: // 得到节点 v 的深度 int depth(TreeNode* root, int curDepth, int v) { if (root == nullptr) return 0; if (root->val == v) { return curDepth; } int x = depth(root->left, curDepth + 1, v); if (x > 0) return x; return depth(root->right, curDepth + 1, v); } // 得到节点 v 的父母 TreeNode* findParent(TreeNode* root, TreeNode* parent, int v) { if (root == nullptr) return nullptr; if (root->val == v) return parent; TreeNode* left = findParent(root->left, root, v); if (left != nullptr) return left; return findParent(root->right, root, v); } };
当然上面的算法假定给定的两个节点都能在树中找到, 否则算法会给出不是的结果(也算正常), 不存在的节点返回高度为0, 父母为NULL.
英文: The Cousins in Binary Tree
相关工具: 家庭关系称呼查讯 – 家庭称谓计算器 – 女儿的儿子的哥哥的老婆叫啥?
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK