题解 | JZ86 在二叉树中找到两个节点的最近公共祖先

最近的公共祖先一定是从根节点开始的一条到目的节点的路径。所以这条路径上一定会包含根节点。因此我们先找到从根节点到两个节点的路径，然后再同时遍历这两条路径，一旦发现，节点不一样的情况立即返回。这样上一个节点就是两个节点最近的公共祖先。

c++
python

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode* find_root = nullptr;
    vector<int> link[2];
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        link[0].push_back(root->val);
        link[1].push_back(root->val);
        
        find_root = nullptr;
        findP(root, o1, 0);
        find_root = nullptr;
        findP(root, o2, 1);
        
        int i;
        for (i=0; i<link[0].size() && i<link[1].size(); i++) {
            if (link[0][i] != link[1][i]) {
                break;   
            }
        }
        return link[0][i-1];
//         return link[0][3];
    }
    
    void findP(TreeNode* root, int val, int op) {
        if (find_root) {
            return;
        }
        if (!root) {
            return;
        }
          
        if (root->val == val) {
            find_root = root;
            return;
        }
        
        if (root->left) {
            link[op].push_back(root->left->val);
            findP(root->left, val, op);
            if (find_root) return;
            link[op].pop_back();
        }
            
        if (root->right) {
            link[op].push_back(root->right->val);
            findP(root->right, val, op);
            if (find_root) return;
            link[op].pop_back();
        }
    }
};

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    
    link = [[], []]
    find_root = None
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        self.link[0].append(root.val)
        self.link[1].append(root.val)
        
        
        self.find_root = None
        self.findP(root, o1, 0)
        self.find_root = None
        self.findP(root, o2, 1)
        
        pos = 0
        for i in range(min(len(self.link[0]), len(self.link[1]))):
            if self.link[0][i] != self.link[1][i]:
                break
            pos += 1
            
            
        return self.link[0][pos - 1]
    
    def findP(self, root: TreeNode, val: int, op: int):
        if self.find_root:
            return 
        
        if not root:
            return
        
        if root.val == val:
            self.find_root = root
            return
        
        if root.left:
            self.link[op].append(root.left.val)
            self.findP(root.left, val, op)
            if self.find_root:
                return
            self.link[op].pop(len(self.link[op]) - 1)
        
        if root.right:
            self.link[op].append(root.right.val)
            self.findP(root.right, val, op)
            if self.find_root:
                return
            self.link[op].pop(len(self.link[op]) - 1)