Java教程

剑指 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. 二叉搜索树的最近公共祖先的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!