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

本文主要是介绍剑指 Offer 68 - I. 二叉搜索树的最近公共祖先，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

注意到这里给出的树是一颗BST树，所以满足有序条件，对于p,q两个节点来说，要找公共祖先且要求深度足够深，所以自然是从root开始找，如果p,q分别位于root的两侧，自然可以说明root是p,q的最近公共祖先，否则，则需要判断p,q是否分别位于root的同一侧，这时就可以通过值来判断，如果p,q的值都比root小，说明此时需要去左子树找公共祖先，否则说明在右子树找公共祖先。
代码如下，这里判断是否位于同一侧用的是做差相减，可以归并几种情况，代码更简洁高效。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode ancestor;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        find(root, p, q);
        return ancestor;
    }
    private void find(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == null) {
            ancestor = root;
            return ;
        }
        // 取出各节点的值
        int pVal = p.val, qVal = q.val, rVal = root.val;
        // 计算p,q两节点与root的差判断是否在同侧
        int diff = (rVal - pVal) * (rVal - qVal);
        // 如果乘积小于0,说明root在p和q的中间,这时可以保证深度最深,所以直接返回root
        if(diff <= 0) {
            ancestor = root;
            return ;
        } else {
            // 乘积小于0,说明p,q在root的同一侧
            if(pVal < rVal) {
                // 如果p的值比root的值小,说明需要去坐标找公共祖先
                find(root.left, p, q);
            } else {
                find(root.right, p, q);
            }
        }
    }
}

时间复杂度\(O(logn)\)，空间复杂度\(O(1)\)。

这篇关于剑指 Offer 68 - I. 二叉搜索树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！