leetcode236-二叉树的最近公共祖先

原题

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

leetcode236-二叉树的最近公共祖先

示例1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

解法

思想

我首先的思路就是要有一个reach函数,可以判断一个节点是不是指定节点的祖先,通过dfs实现,返回一个bool值。
那么这道题要寻找离p、q最近的祖先节点,就可以再使用一个dfs,我们都知道dfs回溯的时候是从下往上的,那么只要调用函数最早对参数p、q都返回true的节点就是要得到的答案了,然后沿着回溯返回值链传回这个节点。

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        if(left!=null) return left;
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(right!=null) return right;
        if(reach(root,p.val)==true&&reach(root,q.val)==true) return root;
        return null;
    }
    public boolean reach(TreeNode root,int value){
        if(root == null) return false;
        if(root.val == value) return true;
        return reach(root.left,value) || reach(root.right,value);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode236-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e6%9c%80%e8%bf%91%e5%85%ac%e5%85%b1%e7%a5%96%e5%85%88/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月14日 21:45
下一篇 2020年1月15日

相关推荐

  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0380
  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0140
  • leetcode83-删除排序链表中的重复元素

    今天打算多刷几道算法题 原题 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->…

    算法 2020年6月16日
    01330
  • leetcode1013-将数组分成和相等的三个部分

    原题 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] +…

    算法 2020年3月11日
    0550
  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0110
  • leetcode494-目标和

    原题 给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。…

    算法 2019年12月12日
    080
  • 程序员面试金典08.01-三步问题

    原题(来源Leetcode) 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模…

    算法 2020年6月19日
    04520
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290
  • leetcode264-丑数II

    原题 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, …

    算法 2020年2月10日
    0170
  • leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。 示例1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例2: 输入…

    2020年2月25日
    0690

发表回复

登录后才能评论