题目
思路
我们可以通过两个栈来实现
实现一个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, stack<TreeNode*>& 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) { stack<TreeNode*> Ppath; // 保存节点p的路径 stack<TreeNode*> 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(); // 返回最低公共祖先节点 } };
(本题完)