本文共 1019 字，大约阅读时间需要 3 分钟。

1. 本题知识点

二叉树、深度优先遍历

2. 题目描述

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

3. 解题思路

最近公共祖先和 o1,o2 有三种关系：

1. o1,o2 分别在祖先左右两侧
2. 祖先是 o1，o2 在祖先左/右侧
3. 祖先是 o2，o1 在祖先左/右侧

使用 dfs 深度遍历，如果节点为 o1,o2 中其中一个直接返回，如果节点超过叶子节点也返回

4. 代码

public class Solution {
       /**     *      * @param root TreeNode类      * @param o1 int整型      * @param o2 int整型      * @return int整型     */    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
           return CommonAncestor(root, o1, o2).val;     }        public TreeNode CommonAncestor (TreeNode root, int o1, int o2) {
           if (root == null || root.val == o1 || root.val == o2) {
    // 超过叶子节点，或者root为o1、o2中的一个直接返回            return root;        }         TreeNode left = CommonAncestor(root.left,o1,o2); // 返回左侧的o1\o2节点        TreeNode right = CommonAncestor(root.right,o1,o2); // 返回右侧的o1\o2节点        if (left == null) {
     // 都在右侧            return right;        }        if (right == null) {
    // 都在左侧            return left;        }        return root; // 在左右两侧    }}

转载地址：http://ccjvb.baihongyu.com/