Leetcode 235/236 Lowest Common Ancestor

Definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

• 寻找两个节点的最低公共祖先(LCA)是非常经典的题目，但是根据具体的树的类型（普通树/二叉树/二叉搜索树）和节点的结构类型（是否包含父节点指针）等，又可以变成多个完全不同思路的题目。
• 很久之前就想整理一下这类题目，最近有空赶紧搞一下。

[Bonus] Lowest Common Ancestor of TreeNode with parent pointer

• 当节点类型内包含父节点指针时，寻找LCA的问题将被转化成寻找两个链表的第一个公共节点的问题。
• 可以考虑在两个栈中用循环分别存放两个节点从自己到根节点的路径，然后在循环中判断两个栈顶是否是相同节点并同时弹出栈顶，直到栈顶节点不同，此时前一次弹出的栈顶节点就是要找的LCA
• 由于此类节点类型带来的特殊性，注意到不论是否是二叉树都可以用这种方法处理

[235] Lowest Common Ancestor of a Binary Search Tree

/* Definition for a binary tree node. */
struct TreeNode {
    int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
};

• 跟上面的问题利用节点结构不同，这道题利用的是二叉搜索树的性质
• 由于二叉搜索树父节点与子节点的值存在明确的逻辑关系，所以并不需要依靠父结点指针，可以直接从根节点开始往下寻找

class Solution {
    
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* cur = root;while (true) {
    if (p->val < cur->val && q->val < cur->val)cur = cur->left;else if (p->val > cur->val && q->val > cur->val)cur = cur->right;elsebreak;}return cur;}
};

[236] Lowest Common Ancestor of a Binary Tree

/* Definition for a binary tree node. */
struct TreeNode {
    int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
};

Solution 1 - 转化为比较熟悉的情况，容易理解

• 这道题跟第一个问题唯一的不同就是节点结构中不包括父节点指针，所以最容易想到的就是通过其他方式获得两条路径
• 获得两条路径的方法有很多，比较常用的是对树进行两次遍历，并维护两个路径，当遍历到目标节点时，就停止遍历
• 获得两条路径后就可以沿用第一个问题的方式进行处理。需要提到的是，这种思路虽然简单，但是不够优雅，效率也不够高。

Solution 2 - 巧妙利用递归，更加优雅

• 下面是这道题最优雅的实现方式了，可惜不是自己想出来的，但是真的elegant
• 具体逻辑不太容易用语言叙述，最好用画图或调试的方式，跟着递归栈走一遍，观察一下在各情况下，递归进行的操作，体会其精妙之处…

class Solution {
    
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root)return root;if (root == p || root == q)return root;TreeNode* leftPtr = lowestCommonAncestor(root->left, p, q);TreeNode* rightPtr = lowestCommonAncestor(root->right, p, q);if (leftPtr && rightPtr)return root;return leftPtr ? leftPtr : rightPtr;}
};

其他

• 关于上述后两个问题在多叉树的实现，由于比较相似，不再单独列出
• 其实还有一些LCA相关的问题，暂时没有整理，如果之后遇到比较典型的相关问题再来整理吧…