Binary Tree - Lowest Common Ancestor 题型总结

2024-09-04 14:32

本文主要是介绍Binary Tree - Lowest Common Ancestor 题型总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Lowest Common Ancestor of a Binary Search Tree

思路:这题跟 Lowest Common Ancestor of Binary Tree 一模一样。思路:就是找p的节点在不在左支,或者右支,找到各自左右节点,然后进行比较,如果两者不一样,说明当前的root就是lowest 父节点,如果左边为空,那就都在右边,返回右边的即可,如果右边为空,那就都在左边,返回左边的即可。

/*** 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 == null) {return null;}if(p == null || q == null) {return root;}TreeNode node = root;while(node != null) {if(node.val < p.val && node.val < q.val) {node = node.right;} else if(node.val > p.val && node.val > q.val) {node = node.left;} else {break;}}return node;}
}

Lowest Common Ancestor of a Binary Tree

思路:lowestCommonAncestor 的定义就是找到的LCA;

如果两者都不为空,说明当前的root就是lowest 父节点,如果左边为空,那就都在右边,返回右边的即可,如果右边为空,那就都在左边,返回左边的即可。

/*** 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 == null || root == p || root == q) {return root;}TreeNode leftnode = lowestCommonAncestor(root.left, p, q);TreeNode rightnode = lowestCommonAncestor(root.right, p, q);if(leftnode == null) {return rightnode;} else if(rightnode == null) {return leftnode;} else {return root;}}
}

Lowest Common Ancestor of Deepest Leaves

  • 题目要求求deepest leaf的LCA,我们首先需要tree depth的信息(注意不是node depth, 也可以理解为deepest leaf depth 也就是tree depth信息),然后跟LCA一样,需要返回node信息,那么我们就需要resultType作为返回值;findLCA 表示当前枝,找到的LCA和它所能找到的deepest leaf 的depth;如果左右depth相等,证明当前node就是LCA;并返回leftnode的depth也就是deepest node的depth;

注意这里有两个表示:一个是method的depth代表node的depth,另外一个returnType里面的depth代表找到的node的 deepest depth;

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private class ReturnType {public TreeNode node;public int depth;public ReturnType(TreeNode node, int depth) {this.node = node;this.depth = depth;}}public TreeNode lcaDeepestLeaves(TreeNode root) {if(root == null) {return null;}ReturnType n = findLCA(root, 0);return n.node;}private ReturnType findLCA(TreeNode root, int depth) {if(root == null) {return new ReturnType(null, depth);}ReturnType leftnode = findLCA(root.left, depth + 1);ReturnType rightnode = findLCA(root.right, depth + 1);if(leftnode.depth == rightnode.depth) {return new ReturnType(root, leftnode.depth);}if(leftnode.depth > rightnode.depth) {return leftnode;} else {return rightnode;}}
}

 

这篇关于Binary Tree - Lowest Common Ancestor 题型总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1136238

相关文章

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象(DAO)和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类(Entity)3.创建数据访问对象(DAO

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000