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

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

展开讨论

我这里贡献一个解法
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
展开全部 3 讨论