中铁建设投资集团有限公司招聘网站,微信开放平台官方网站,做英文版网站,下述不属于网页制作工具二叉树的最近公共祖先 题目思路代码#xff08;详细注释#xff09; 题目 二叉树的最近公共祖先 思路
我们可以通过两个栈来实现
实现一个FindPath函数#xff0c;用来查找从根节点到目标节点的路径#xff08;路径可以用栈来保存#xff09;
路径保存好后#xff0c;… 二叉树的最近公共祖先 题目思路代码详细注释 题目 二叉树的最近公共祖先 思路
我们可以通过两个栈来实现
实现一个FindPath函数用来查找从根节点到目标节点的路径路径可以用栈来保存
路径保存好后 再使用两个循环来比较栈Ppath和Qpath的大小使得两个栈的大小相等。 然后再使用一个循环来比较栈顶元素直到找到最低公共祖先。在每一次比较过程中如果栈顶元素不相等就分别从两个栈中弹出栈顶元素直到找到最低公共祖先。
操作如下 在lowestCommonAncestor函数中声明两个栈Ppath和Qpath用于保存从根节点到节点p和q的路径。 调用FindPath函数两次分别查找节点p和q的路径。FindPath函数是一个递归函数用于在二叉树中查找节点x的路径并将路径保存在给定的栈path中。 在FindPath函数中首先判断当前节点root是否为空如果为空则返回false。然后将当前节点root压入栈path中。 接着判断当前节点root是否等于目标节点x如果是则返回true表示已经找到目标节点。 如果目标节点不在当前节点root上那么就递归地在左子树和右子树中查找目标节点。如果在左子树中找到目标节点则返回true表示已经找到目标节点。如果在右子树中找到目标节点则同样返回true。 如果左子树和右子树都没有找到目标节点则说明当前节点不在最终路径上需要将其从栈path中弹出并返回false。 回到lowestCommonAncestor函数使用两个循环来比较栈Ppath和Qpath的大小使得两个栈的大小相等。 然后再使用一个循环来比较栈顶元素直到找到最低公共祖先。在每一次比较过程中如果栈顶元素不相等就分别从两个栈中弹出栈顶元素直到找到最低公共祖先。 最后返回栈Qpath的栈顶元素即为最低公共祖先节点。
代码详细注释
class Solution {
public:// 查找从根节点到目标节点的路径bool FindPath(TreeNode *root, TreeNode *x, stackTreeNode* path) {if (root nullptr) {return false; // 当前节点为空返回false}path.push(root); // 将当前节点加入路径if (x root) {return true; // 找到目标节点返回true}if (FindPath(root-left, x, path)) {return true; // 在左子树中找到目标节点返回true}if (FindPath(root-right, x, path)) {return true; // 在右子树中找到目标节点返回true}path.pop(); // 当前节点不在路径上弹出当前节点return false; // 返回false}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* Ppath; // 保存节点p的路径stackTreeNode* Qpath; // 保存节点q的路径FindPath(root, p, Ppath); // 查找节点p的路径FindPath(root, q, Qpath); // 查找节点q的路径// 使得两个路径的长度相等while (Ppath.size() ! Qpath.size()) {if (Ppath.size() Qpath.size()) {Ppath.pop(); // 如果Ppath路径长弹出Ppath的栈顶元素} else {Qpath.pop(); // 如果Qpath路径长弹出Qpath的栈顶元素}}// 逐个比较两个路径上的节点找到最低公共祖先while (Ppath.top() ! Qpath.top()) {Qpath.pop(); // 弹出Qpath栈顶元素Ppath.pop(); // 弹出Ppath栈顶元素}return Qpath.top(); // 返回最低公共祖先节点}
};本题完
