|
在职场中打听别人工资是很忌讳的，所以公司的薪资一般都是保密的，如果不保密，当你知道一个能力不如你的比你工资还高的时候，心里就会产生不平衡，工作可能就会没那么积极了。 下面是一位网友打听同事的薪资，这一问一答彰显功力非凡，有的网友说了：薪资保密是利于公司不利于员工的，好像说的也对。 --------------下面是今天的算法题-------------- 来看下今天的算法题，这题是LeetCode的第993题：二叉树的堂兄弟节点。 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。如果二叉树的两个节点深度相同，但父节点不同 ，则它们是一对堂兄弟节点。 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。 输入：root = [1,2,3,4], x = 4, y = 3 输出：false
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4 输出：true
这题让判断两个节点是否是堂兄弟节点，如果这两个节点在同一层，并且他们的父节点不同，他们就是堂兄弟节点，否则就不是。
所以我们只需要找到这两个节点的深度以及他们的父节点即可，使用DFS或者是BFS都可以，如果两个节点都找到了，直接终止查找，最后在比较他们的深度和父节点。
private TreeNode xParent = null;// x的父节点
private TreeNode yParent = null;// y的父节点
private int xDepth = -1;// x的深度
private int yDepth = -2;// y的深度
public boolean isCousins(TreeNode root, int x, int y) {
dfs(root, null, x, y, 0);
// 如果他俩的深度一样，也就是在同一层，又不是同一个父亲，那么他俩
// 就是堂兄弟节点，否则不是
return xDepth == yDepth && xParent != yParent;
}
public void dfs(TreeNode root, TreeNode parent, int x, int y, int depth) {
if (root == null)
return;
if (root.val == x) {
// 如果找到了x节点，就把他的父节点和深度记录下来
xParent = parent;
xDepth = depth;
} else if (root.val == y) {
// 如果找到了y节点，就把他的父节点和深度记录下来
yParent = parent;
yDepth = depth;
}
// 如果两个节点的父节点都找到了，直接返回，不用再往下遍历了
if (xParent != null && yParent != null)
return;
dfs(root.left, root, x, y, depth + 1);
dfs(root.right, root, x, y, depth + 1);
}
private:
TreeNode *xParent = nullptr;// x的父节点
TreeNode *yParent = nullptr;// y的父节点
int xDepth = -1;// x的深度
int yDepth = -2;// y的深度
public:
bool isCousins(TreeNode *root, int x, int y) {
dfs(root, nullptr, x, y, 0);
// 如果他俩的深度一样，也就是在同一层，又不是同一个父亲，那么他俩
// 就是堂兄弟节点，否则不是
return xDepth == yDepth && xParent != yParent;
}
void dfs(TreeNode *root, TreeNode *parent, int x, int y, int depth) {
if (root == nullptr)
return;
if (root->val == x) {
// 如果找到了x节点，就把他的父节点和深度记录下来
xParent = parent;
xDepth = depth;
} else if (root->val == y) {
// 如果找到了y节点，就把他的父节点和深度记录下来
yParent = parent;
yDepth = depth;
}
// 如果两个节点的父节点都找到了，直接返回，不用再往下遍历了
if (xParent && yParent)
return;
dfs(root->left, root, x, y, depth + 1);
dfs(root->right, root, x, y, depth + 1);
}
struct TreeNode *xParent;// x的父节点
struct TreeNode *yParent;// y的父节点
int xDepth;// x的深度
int yDepth;// y的深度
void dfs(struct TreeNode *root, struct TreeNode *parent, int x, int y, int depth) {
if (!root)
return;
if (root->val == x) {
// 如果找到了x节点，就把他的父节点和深度记录下来
xParent = parent;
xDepth = depth;
} else if (root->val == y) {
// 如果找到了y节点，就把他的父节点和深度记录下来
yParent = parent;
yDepth = depth;
}
// 如果两个节点的父节点都找到了，直接返回，不用再往下遍历了
if (xParent && yParent)
return;
dfs(root->left, root, x, y, depth + 1);
dfs(root->right, root, x, y, depth + 1);
}
bool isCousins(struct TreeNode *root, int x, int y) {
xParent = NULL;// x的父节点
yParent = NULL;// y的父节点
xDepth = -1;// x的深度
yDepth = -2;// y的深度
dfs(root, NULL, x, y, 0);
// 如果他俩的深度一样，也就是在同一层，又不是同一个父亲，那么他俩
// 就是堂兄弟节点，否则不是
return xDepth == yDepth && xParent != yParent;
}
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
xParent, yParent = None, None # x,y的父节点
xDepth, yDepth = -1, -2 # x,y的深度
def dfs(node: TreeNode, parent: TreeNode, depth: int):
if not node:
return
nonlocal xParent, yParent, xDepth, yDepth
if node.val == x:
# 如果找到了x节点，就把他的父节点和深度记录下来
xParent, xDepth = parent, depth
elif node.val == y:
# 如果找到了y节点，就把他的父节点和深度记录下来
yParent, yDepth = parent, depth
# 如果两个节点的父节点都找到了，直接返回，不用再往下遍历了
if xParent and yParent:
return
dfs(node.left, node, depth + 1)
dfs(node.right, node, depth + 1)
dfs(root, None, 0)
# 如果他俩的深度一样，也就是在同一层，又不是同一个父亲，那么他俩
# 就是堂兄弟节点，否则不是
return xDepth == yDepth and xParent != yParent
博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。
|
