ChunNote
0%

leetCode-235:Lowest Common Ancestor of a Binary Search Tree

发表于 分类于

问题描述

给定一个搜索二叉树和两个节点，要求找出两个节点的公共祖先。题目链接：点我

样例输入输出

输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出：6

解释：树的形状如下

binarysearchtree_improved.png (200×190) (leetcode.com)

输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出：2

解释：树的形状如下

binarysearchtree_improved.png (200×190) (leetcode.com)

问题解法

树是二叉搜索树，可以充分利用这个特点进行搜索，如果 p 和 q 在根节点的左右两边或其中一个节点是根节点，那么这两个节点的最近公共祖先就是根节点，如果 p 和 q 的值都小于根节点的值，那么其最近公共祖先就在左子树中，此时递归搜索左子树即可，如果 p 和 q 的值都大于根节点的值，那么其最近公共祖先就在右子树中，此时递归搜索右子树即可。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val == p.val || root.val == q.val) {
            return root;
        }

        TreeNode small;
        TreeNode big;
        if (p.val < q.val) {
            small = p;
            big = q;
        } else {
            small = q;
            big = p;
        }
        
        if (small.val < root.val && root.val < big.val) {
            return root;
        }
        
        if (big.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        
        return lowestCommonAncestor(root.right, p, q);
    }
}