首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:首个共同祖先

#yyds干货盘点# LeetCode程序员面试金典:首个共同祖先

时间:2022-12-25 13:02:21浏览次数:44  
标签:yyds TreeNode val 金典 节点 ans null root LeetCode

题目:

设计并实现一个算法,找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意:这不一定是二叉搜索树。

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

   3

  / \

 5   1

/ \ / \

6  2 0  8

 / \

7   4

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

代码实现:

class Solution {

private TreeNode ans;

public Solution() {
this.ans = null;
}

private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}

标签:yyds,TreeNode,val,金典,节点,ans,null,root,LeetCode
From: https://blog.51cto.com/u_13321676/5968106

相关文章

  • #yyds干货盘点# 名企真题专题:将满二叉树转换为求和树
    1.简述:描述给出满二叉树的前序遍历结果和中序遍历结果,编写算法将其转化为求和树什么是求和树:二叉树的求和树,是一颗同样结构的二叉树,其树中的每个节点将包含原始树中的左子......
  • [LeetCode] 2389. Longest Subsequence With Limited Sum
    Youaregivenanintegerarray nums oflength n,andanintegerarray queries oflength m.Return anarray answer oflength m where answer[i] ist......
  • leetcode-14最长公共前缀
    14.最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串""。示例1:输入:strs=["flower","flow","flight"]输出:"fl"示例2:输入:s......
  • [LeetCode] 790. Domino and Tromino Tiling
    Youhavetwotypesoftiles:a 2x1 dominoshapeandatrominoshape.Youmayrotatetheseshapes.Givenanintegern,return thenumberofwaystotilea......
  • [LeetCode] 1754. Largest Merge Of Two Strings
    Youaregiventwostrings word1 and word2.Youwanttoconstructastring merge inthefollowingway:whileeither word1 or word2 arenon-empty,choos......
  • Leetcode61
    !!Giventhe head ofalinked list,rotatethelisttotherightby k places.!! # Definition for singly-linked list.# class ListNode(object):# ......
  • #yyds干货盘点# LeetCode程序员面试金典:合法二叉搜索树
    题目:实现一个函数,检查一棵二叉树是否为二叉搜索树。示例 1:输入:  2 /\ 1 3输出:true示例 2:输入:  5 /\ 1 4  /\  3 6输出:fa......
  • leetcode-520. 检测大写字母
    520.检测大写字母-力扣(Leetcode)unicode包里面有IsUpper方法可以用来判断是否是大写字母funcdetectCapitalUse(wordstring)bool{iflen(word)<=1{......
  • leetcode笔记——324周赛
    第三题中设置字典:G = defaultdict(set)这样默认每个item是个set,可以直接用G[i].add(),不用G.get()再判断了第三题中有个判断:return any(i != x and i!=y and......
  • leetcode-12整数转罗马数字
    12.整数转罗马数字罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D......