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

题目的主要信息：

• 给定一棵二叉树以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点
• 二叉树非空，且每个节点值均不同

举一反三：

学习完本题的思路你可以解决如下题目：

BM29. 二叉树中和为某一值的路径（一）

BM37. 二叉搜索树的最近公共祖先

方法一：路径比较法(推荐使用)

知识点：深度优先搜索（dfs）

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路：

既然要找到二叉树中两个节点的最近公共祖先，那我们可以考虑先找到两个节点全部祖先，可以得到从根节点到目标节点的路径，然后依次比较路径得出谁是最近的祖先。

找到两个节点的所在可以深度优先搜索遍历二叉树所有节点进行查找。

具体做法：

• step 1：利用dfs求得根节点到两个目标节点的路径：每次选择二叉树的一棵子树往下找，同时路径数组增加这个遍历的节点值。
• step 2：一旦遍历到了叶子节点也没有，则回溯到父节点，寻找其他路径，回溯时要去掉数组中刚刚加入的元素。
• step 3：然后遍历两条路径数组，依次比较元素值。
• step 4：找到两条路径第一个不相同的节点即是最近公共祖先。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    //记录是否找到到o的路径
    public boolean flag = false; 
    //求得根节点到目标节点的路径
    public void dfs(TreeNode root, ArrayList<Integer> path, int o){ 
        if(flag || root == null)
            return;
        path.add(root.val);
        //节点值都不同，可以直接用值比较
        if(root.val == o){ 
            flag = true;
            return;
        }
        //dfs遍历查找
        dfs(root.left, path, o); 
        dfs(root.right, path, o);
        //找到
        if(flag)
            return;
        //回溯
        path.remove(path.size() - 1);
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>(); 
        ArrayList<Integer> path2 = new ArrayList<Integer>(); 
        //求根节点到两个节点的路径
        dfs(root, path1, o1); 
        //重置flag，查找下一个
        flag = false; 
        dfs(root, path2, o2);
        int res = 0; 
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++){ 
            int x = path1.get(i);
            int y = path2.get(i);
            if(x == y) 
                //最后一个相同的节点就是最近公共祖先
                res = x; 
            else
                break;
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    //记录是否找到到o的路径
    bool flag = false; 
    //求得根节点到目标节点的路径
    void dfs(TreeNode* root, vector<int>& path, int o){ 
        if(flag || root == NULL)
            return;
        path.push_back(root->val);
        //节点值都不同，可以直接用值比较
        if(root->val == o){ 
            flag = true;
            return;
        }
        //dfs遍历查找
        dfs(root->left, path, o); 
        dfs(root->right, path, o);
        //找到
        if(flag)
            return;
        //该子树没有，回溯
        path.pop_back(); 
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> path1, path2; 
        //求根节点到两个节点的路径
        dfs(root, path1, o1); 
        //重置flag，查找下一个
        flag = false; 
        dfs(root, path2, o2);
        int res; 
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++){ 
            if(path1[i] == path2[i]) 
                //最后一个相同的节点就是最近公共祖先
                res = path1[i]; 
            else
                break;
        }
        return res;
    }
};

Python实现代码

class Solution:
    # 记录是否找到到o的路径
    flag = False 
    # 求得根节点到目标节点的路径
    def dfs(self, root: TreeNode, path: List[int], o: int): 
        if self.flag or not root:
            return
        path.append(root.val)
        # 节点值都不同，可以直接用值比较
        if root.val == o: 
            self.flag = True
            return
        # dfs遍历查找
        self.dfs(root.left, path, o) 
        self.dfs(root.right, path, o)
        #找到
        if self.flag:
            return
        # 该子树没有，回溯
        path.pop() 
        
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        path1, path2 = [], []
        # 求根节点到两个节点的路径
        self.dfs(root, path1, o1) 
        # 重置flag，查找下一个
        self.flag = False 
        self.dfs(root, path2, o2)
        i = 0
        res = None
        # 比较两个路径，找到第一个不同的点
        while i < len(path1) and i < len(path2): 
            if path1[i] == path2[i]: 
                # 最后一个相同的节点就是最近公共祖先
                res = path1[i] 
                i += 1
            else:
                break
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树节点数，递归遍历二叉树每一个节点求路径，后续又遍历路径
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，深度为$nn$，递归栈深度和路径数组为$nn$

方法二：递归（扩展思路）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

我们也可以讨论几种情况：

• step 1：如果o1和o2中的任一个和root匹配，那么root就是最近公共祖先。
• step 2：如果都不匹配，则分别递归左、右子树。
• step 3：如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先.
• step 4：如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。
• step 5：继续递归左、右子树，直到遇到step1或者step3的情况。

Java实现代码：

import java.util.*;
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //该子树没找到，返回-1
        if(root == null) 
            return -1;
        //该节点是其中某一个节点
        if(root.val == o1 || root.val == o2) 
            return root.val;
        //左子树寻找公共祖先
        int left = lowestCommonAncestor(root.left, o1, o2); 
        //右子树寻找公共祖先
        int right = lowestCommonAncestor(root.right, o1, o2); 
        //左子树为没找到，则在右子树中
        if(left == -1) 
            return right;
        //右子树没找到，则在左子树中
        if(right == -1) 
            return left;
        //否则是当前节点
        return root.val; 
    }
}

C++实现代码：

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        //该子树没找到，返回-1
        if(root == NULL) 
            return -1;
        //该节点是其中某一个节点
        if(root->val == o1 || root->val == o2) 
            return root->val;
        //左子树寻找公共祖先
        int left = lowestCommonAncestor(root->left, o1, o2); 
        //右子树寻找公共祖先
        int right = lowestCommonAncestor(root->right, o1, o2); 
        //左子树为没找到，则在右子树中
        if(left == -1) 
            return right;
        //右子树没找到，则在左子树中
        if(right == -1) 
            return left;
        //否则是当前节点
        return root->val; 
    }
};

Python实现代码

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # 该子树没找到，返回-1
        if not root: 
            return -1
        # 该节点是其中某一个节点
        if root.val == o1 or root.val == o2: 
            return root.val
        # 左子树寻找公共祖先
        left = self.lowestCommonAncestor(root.left, o1, o2) 
        # 右子树寻找公共祖先
        right = self.lowestCommonAncestor(root.right, o1, o2) 
        # 左子树为没找到，则在右子树中
        if left == -1: 
            return right
        # 右子树没找到，则在左子树中
        if right == -1: 
            return left
        # 否则是当前节点
        return root.val 

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为节点数，递归遍历二叉树每一个节点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，递归栈深度为$nn$