讨论/算法和数据结构/判断⼆叉树中结点是否存在祖孙关系/
判断⼆叉树中结点是否存在祖孙关系

判断以 root 为根的⼆叉树中结点 a 和结点 b 是否存在祖孙关系,若存在 祖孙关系,则输出其祖先到⼦孙之间的路径。

共 3 个回复

我这里贡献一个解法
1,先找到最近公共父节点p
2,如果p既不是a也不是b,那ab就不是祖孙关系
3,如果是其中一个,dfs的方式去寻找他们的路径
时间复杂度O(n),空间复杂度取决于树的深度
以下代码我已经本地单测了几个人工构造的例子,都通过了,可以参考哈

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(NULL), right(NULL) {};
	TreeNode(int v) : val(v), left(NULL), right(NULL) {};
};

TreeNode* LCA(TreeNode* root, TreeNode* a, TreeNode* b) {
	if (root == NULL || root == a || root == b) return root;
	auto l = LCA(root->left, a, b);
	auto r = LCA(root->right, a, b);
	if (l == NULL) return r;
	if (r == NULL) return l;
	return root;
}
void dfs(TreeNode* from, TreeNode* to, vector<TreeNode*>& path, vector<TreeNode*>& res) {
	if (from == NULL || !res.empty()) return;
	if (from == to) {
		path.push_back(from);
		res = path;
		return;
	}
	path.push_back(from);
	dfs(from->left, to, path, res);
	dfs(from->right, to, path, res);
	path.pop_back();
}
vector<TreeNode*> CheckAndFindPath(TreeNode* root, TreeNode* a, TreeNode* b) {
	auto p = LCA(root, a, b);
	if (p != a && p != b) return {};
	vector<TreeNode*> path;
	vector<TreeNode*> res;
	if (p == a) {
		dfs(a, b, path, res);
	} else {
		dfs(b, a, path, res);
	}
	return res;
}
1

做一次dfs,记录结点的父亲结点和位于第几层。假设结点a位于L(a)层,结点b位于L(b)层,L(a)>=L(b)L(a) >= L(b),那么从结点a开始向上遍历,遍历到结点a的祖先中位于L(b)层的结点,如果这个就是b,那么b就是a的祖先,如果不是,那么这倆结点没有祖孙关系

  1. 如果题目只需要查询一组a和b,那么就是上面分析的做法,复杂度是o(n)
  2. 如果题目需要查询多组a和b,那么上面分析的做法以外,还要做一次倍增算法,就是每个结点,预处理这个结点的第1个祖先,第2个祖先,第4个祖先,第8个祖先。。。。以便可以用log(h)的复杂度查询结点a和结点b是否祖孙关系