leetcode 236. 二叉树的最近公共祖先

leetcode 236. 二叉树的最近公共祖先

题目

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

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

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1

提示:
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路

一开始我是想着正常递归遍历,然后记录一下搜索路径,然后遇到p或者q就记录找到了(flag=true)然后一直回退就完了。但是需要注意递归结束要remove的,否则记录的是递归顺序而不是从根节点到当前的搜索顺序。remove前的if(flag)也很重要,这表示找到了,就别remove了。然后对比p和q的路径就完了。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {boolean flag = false;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode> pList = new ArrayList<TreeNode>();List<TreeNode> qList = new ArrayList<TreeNode>();dfs(root, pList, p);flag = false;dfs(root, qList, q);TreeNode res = new TreeNode();for (int i=0;i<Math.min(pList.size(), qList.size());i++) {if (pList.get(i) == qList.get(i)) {res = pList.get(i);}else {break;}}return res;}public void dfs(TreeNode root, List<TreeNode> list, TreeNode node) {if (flag || root == null) {list.add(null);return;}list.add(root);if (root == node) {flag = true;return;}dfs(root.left, list, node);if (flag) {return;}list.remove(list.size() - 1);dfs(root.right, list, node);if (flag) {return;}list.remove(list.size() - 1);}
}

在这里插入图片描述
但这个结果太拉了,其实是有更好的方法的。那就是p和q往上递归搜索,找到同一个节点就结束了。其实这就是后续遍历的用处,左右中。
这里我们来聊聊递归的写法细节,首先肯定我们知道是先写一个判断递归中止的函数。那其他的呢有没有返回值怎么判断,这里可以告诉大家:
1 如果需要搜索整棵二叉树且不用处理递归返回值,递归函数就不要返回值。
2 如果需要搜索整棵二叉树且需要处理递归返回值,递归函数就需要返回值。
3 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就要及时返回。
2的写法是

if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

3的写法是

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。

代码

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/218552.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

4G无线工业级路由器在智能制造设备互联互通中的角色

随着工业技术的不断发展和进步&#xff0c;智能制造已经成为了现代制造业的重要趋势和发展方向。而在智能制造过程中&#xff0c;设备之间的互联互通是至关重要的一环。在这个过程中&#xff0c;4G无线工业级路由器扮演着重要的角色&#xff0c;它提供了稳定可靠的网络连接&…

Vue3项目中集成mars3D简单三部曲

Vue3项目中集成mars3D简单三部曲 这里是参考网址&#xff0c;大佬可以点击一件跳转 1.安装依赖 npm install vite-plugin-mars3d --save-dev2.修改 vite.config.ts 配置文件 import { defineConfig } from vite; import { mars3dPlugin } from vite-plugin-mars3d;export d…

Go开发运维:Go服务发布到K8S集群

目录 一、实验 1.Go服务发布到k8s集群 二、问题 1.如何从Harbor拉取镜像 一、实验 1.Go服务发布到k8s集群 &#xff08;1&#xff09;linux机器安装go(基于CentOS 7系统) yum install go -y &#xff08;2&#xff09;查看版本 go version &#xff08;3&#xff09;创…

vue3 setup语法糖写法基本教程

前言 官网地址&#xff1a;Vue.js - 渐进式 JavaScript 框架 | Vue.js (vuejs.org)下面只讲Vue3与Vue2有差异的地方&#xff0c;一些相同的地方我会忽略或者一笔带过与Vue3一同出来的还有Vite&#xff0c;但是现在不使用它&#xff0c;等以后会有单独的教程使用。目前仍旧使用v…

GZ015 机器人系统集成应用技术样题3-学生赛

2023年全国职业院校技能大赛 高职组“机器人系统集成应用技术”赛项 竞赛任务书&#xff08;学生赛&#xff09; 样题3 选手须知&#xff1a; 本任务书共 26页&#xff0c;如出现任务书缺页、字迹不清等问题&#xff0c;请及时向裁判示意&#xff0c;并进行任务书的更换。参赛队…

自定义日志打印功能--C++

一、介绍 日志是计算机程序中用于记录运行时事件和状态的重要工具。通过记录关键信息和错误情况&#xff0c;日志可以帮助程序开发人员和维护人员追踪程序的执行过程&#xff0c;排查问题和改进性能。 在软件开发中&#xff0c;日志通常记录如下类型的信息&#xff1a; 事件信…

Go delve调试工具的简单应用

Delve是个啥 Delve is a debugger for the Go programming language. The goal of the project is to provide a simple, full featured debugging tool for Go. Delve should be easy to invoke and easy to use. Chances are if you’re using a debugger, things aren’t go…

openmediavault debian linux安装配置企业私有网盘(三 )——raid5与btrfs文件系统无损原数据扩容

一、适用环境 1、企业自有物理专业服务器&#xff0c;一些敏感数据不外流时&#xff0c;使用openmediavault自建NAS系统&#xff1b; 2、在虚拟化环境中自建NAS系统&#xff0c;用于内网办公&#xff0c;或出差外网办公时&#xff0c;企业内的文件共享&#xff1b; 3、虚拟化环…

数据结构-迷宫问题

文章目录 1、题目描述2、题目分析3、代码实现 1、题目描述 题目链接&#xff1a;迷宫问题 、 注意不能斜着走&#xff01; 2、题目分析 &#xff08;1&#xff09;0为可以走&#xff0c;1不能走且只有唯一一条通路 &#xff08;2&#xff09;我们可以通过判断上下左右来确定…

AI智能化办公:ChatGPT使用方法与技巧

文章目录 ChatGPT简介✨ChatGPT的使用方法✨登录与访问发送请求调整参数 ChatGPT技巧分享✨清晰的提问实验不同的温度值多轮对话 图书推荐✨AI智能化办公内容简介获取方式 AI短视频内容简介获取方式 随着人工智能技术的不断发展&#xff0c;AI助手在办公场景中扮演着越来越重要…

基于Python自动化测试框架之接口测试

上一篇阐述了关于web UI相关的内容&#xff0c;这篇谈谈关于接口测试及自动化测试框架。 接口测试是测试系统组件间数据交互的一种方式&#xff0c;通过不同情况下的输入参数和与之对应的输出结果来判断接口是否符合或满足相应的功能性、安全性要求。简单来说&#xff0c;接口…

UE5 - ArchvizExplorer与Map Border Collection结合 - 实现电子围栏效果

插件地址&#xff1a; https://www.unrealengine.com/marketplace/zh-CN/product/archviz-explorer https://www.unrealengine.com/marketplace/zh-CN/product/map-border-collection ArchvizExplorer扩展&#xff1a; https://download.csdn.net/download/qq_17523181/8843305…

Power BI - 5分钟学习增加索引列

每天5分钟&#xff0c;今天介绍Power BI增加索引列。 什么是增加索引列&#xff1f; 增加索引列就是向表中添加一个具有显式位置值的新列&#xff0c;一般从0或者从1开始。 举例&#xff1a; 首先&#xff0c;导入一张【Sales】样例表(Excel数据源导入请参考每天5分钟第一天)…

消除非受检警告

在Java中&#xff0c;有一些情况下编译器会生成非受检警告&#xff08;Unchecked Warnings&#xff09;。这些警告通常与泛型、类型转换或原始类型相关。消除这些警告可以提高代码的可读性和安全性。以下是一些常见的非受检警告以及如何消除它们的例子&#xff1a; 1. 泛型类型…

【K8S 系列】认识k8s、k8s架构

一、什么是k8s? Kubernetes 简称 k8s&#xff0c;是支持云原生部署的一个平台&#xff0c;k8s 本质上就是用来简化微服务的开发和部署的&#xff0c;用于自动化部署、扩展和管理容器化应用的开源容器编排技术。对于传统的docker其实也提供了容器编排的技术docker-compose&…

机器学习---Boosting

1. Boosting算法 Boosting思想源于三个臭皮匠&#xff0c;胜过诸葛亮。找到许多粗略的经验法则比找到一个单一的、高度预 测的规则要容易得多&#xff0c;也更有效。 预测明天是晴是雨&#xff1f;传统观念&#xff1a;依赖于专家系统&#xff08;A perfect Expert) 以“人无…

学习git后,真正在项目中如何使用?

文章目录 前言下载和安装Git克隆远程仓库PyCharm链接本地Git创建分支修改项目工程并提交到本地仓库推送到远程仓库小结 前言 网上学习git的教程&#xff0c;甚至还有很多可视化很好的git教程&#xff0c;入门git也不是什么难事。但我发现&#xff0c;当我真的要从网上克隆一个…

2044回文字符串(C语言)

目录 一&#xff1a;题目 二&#xff1a;思路分析 1.什么是回文&#xff1f; 2.判断回文&#xff1a; 三&#xff1a;代码 一&#xff1a;题目 二&#xff1a;思路分析 1.什么是回文&#xff1f; 最简单的理解方式就是一个字符串正着写和倒着写一样 2.判断回文&#xff1…

leetcode砍竹子1

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段&#xff0c;每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。 1.根据公式看出取等是在所有n相等的情况&#xff0c;可以得出只有均分 乘积最大 2.转为求下面的最大值 3.求导&#xff0c;得出驻点为e2.7左右 …

百度地图中显示红点

initMap(longitude, latitude) {var map new BMapGL.Map("container");// 创建地图实例if (longitude null || latitude null) {var point new BMapGL.Point(111.1480354849708, 37.5262978563336);var marker new BMapGL.Marker(point);map.addOverlay(marker)…