递归-在二叉树中找到两个节点的最近公共祖先

在这里插入图片描述

求解代码

前文【非递归】二叉搜索树的最近公共祖先我们利用非递归+迭代的方式求出了二叉搜索树的最近公共祖先，主要还是利用了二叉搜索树左子树所有节点值<根节点值<右子树所有节点值的特性。

但是，普通二叉树的节点值没有这样的规律，没办法通过数值的大小进行位置的判断力。

本文使用递归的方式求普通二叉树的最近公共祖先：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        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;

    }