算法

LeetCode题解:二叉搜索树的最近公共祖先

2022-07-14  本文已影响0人  搬码人

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

示例

以下两例的示例图都是这个


image.png

输入:{7,1,12,0,4,11,14,#,#,3,5},1,12
输出:7
说明:节点1 和 节点12的最近公共祖先是7

输入:{7,1,12,0,4,11,14,#,#,3,5},12,11
输出:12
说明:因为一个节点也可以是它自己的祖先.所以输出12

思路

二叉搜索树没有相同的节点,因此分别从根节点往下利用二叉搜索树较大的数在右子树,较小的数在左子树,可以轻松找到p、q。

//节点值都不同,可以直接用值比较
while(node.val != target) { 
    path.add(node.val);
    //小的在左子树
    if(target < node.val) 
        node = node.left;
    //大的在右子树
    else 
        node = node.right;
}

步骤:

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    //收集到target的路径
    public ArrayList<Integer> getPath(TreeNode root,int target){
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        while(node.val != target){
            path.add(node.val);
            if(target<node.val){
                node = node.left;
            }else{
                node = node.right;
            }
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //记录路径
        ArrayList<Integer> p_path = getPath(root,p);
        ArrayList<Integer> q_path = getPath(root,q);
        int res = 0;
        for(int i = 0; i < p_path.size() && i < q_path.size(); i++){
            int x = p_path.get(i);
            int y = q_path.get(i);
            //最后一个相同的节点就是最近公共祖先
            if(x == y)
                res = x;
            else
                break;
        }
        return res;
    }
}

通知

小编最近可能要转战Hexo搭建自己的博客,Hexo搭建起来的博客不仅界面舒服,而且可以轻松地根据标签和分类查看想看的内容,并且每篇文章还能根据旁边的目录定位到对应位置。
小编已经搭建的差不多了,如果准备好了会在简书中放地址。

上一篇下一篇

猜你喜欢

热点阅读