剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

Offer_68_1

题目描述

方法一：迭代法

由于该题的二叉树属于排序二叉树，所以相对较简单。
只需要判断两个结点是否在根节点的左右子树中，这可以通过值的大小来判断。
不断迭代左右子树即可得到结果。

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2021/2/15 23:29

 */

/**

 * 题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

 */

/**

 * 方法一：循环迭代法

 */

public class Offer_68_1 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        while(root!=null){

            int val = root.val;

            if(p.val>val && q.val>val)

                root = root.right;

            else if(p.val<val && q.val<val)

                root = root.left;

            else break;

        }

        return root;

    }

}

方法二：递归法

/**

 * 方法二：递归法

 */

class Offer_68_2 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        int val = root.val;

        if(p.val>val && q.val>val)

            return lowestCommonAncestor(root.right, p, q);

        else if(p.val<val && q.val<val)

            return lowestCommonAncestor(root.left, p, q);

        else return root;

    }

}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 + 二叉排序树 + 最近公共祖先的相关教程结束。