算法:在二叉树中寻找两个节点的共同祖先_csmips的博客-程序员信息网_二叉树共同祖先

技术标签: 算法和数据结构  算法  二叉树  

问题:已知二叉树root和两个节点p和q,要求找出p和q在root中的最早的共同祖先。要求:该二叉树的节点没有parent指针(如果有parent指针,算法会简单很多)。


算法思想:中序访问二叉树,对于当前节点,当其左子树和右子树访问完毕,且p与q都已经访问过,则当前节点就是p与q的共同祖先。


算法伪码:

commonAncestor = null;

int inorder(node)
{
  if (node == null)
    return 0;

  if (commonAncesotr)  // found
    return 0;

  // 处理左子树
  int left = inorder(node->l);

  // 处理当前节点
  int in = 0;
  if (node == p || node == q)
    in = 1;

  // 处理右子树
  int right = inorder(node->r);
  
  int sum = left + in + right;

  // 左右子树都处理完毕,当前节点也处理完毕。检查sum,如果sum == 2,说明p和q都访问过了,当前节点就是commonAncestor。
  if (sum == 2)
  {
      commonAncestor = node;
      return 0;
  }

  return sum;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/csmips/article/details/77878234

智能推荐

java语言实现求n个数的最小公倍数和最大公约数_顾彼的博客-程序员信息网

/*一、 题目内容: 求n个数的最小公倍数和最大公约数.用C++或C或java来实现程序解决问题1. 程序风格良好,(使用自定义注释模板)2. 提供友好的输入输出并进行数据的正确性验证*/package com.uplooking1;public class Homework { public Homework() { } public int gcd(i...

Windows下Keras报错TypeError: <lambda>() got an unexpected keyword argument 'name'_剪到手杰克的博客-程序员信息网

Keras 报错 TypeError: lambda() got an unexpected keyword argument ‘name’环境Windows10 x64Keras 0.3.3Theano 0.8.0这种情况貌似只发生在Windows系统下用Keras跑部分实例代码时,lambda表达式引起的错误。 以Keras的示例代码mnist_irnn.py为例,直

Windows下如何搭建FTP服务并且设置其用户名和密码_strong tyj的博客-程序员信息网_windows服务器 创建ftp用户名和密码

1. 为了设置用户名和密码,要做一些准备工作:打开 右键 计算机-》管理-》本地用户和组右键之后点击新用户:设置你自己的用户名和密码,这个就是之后给ftp服务用的。2. 控制面板-》程序和功能-》打开或关闭Windows功能,勾选如下选项进行安装ftp与IIS:3. 打开IIS管理器。控制面板-》管理工具-》信息服务(IIS)管理器4. 进行一下设置。...

谷歌浏览器清空缓存并硬性重新加载_小小野猪的博客-程序员信息网

很多时候右键点击谷歌浏览器左上角刷新按钮不能显示出来"清空缓存并硬性重新加载";少了一个必要条件: 点击F12,然后再右键点击谷歌浏览器左上角刷新按钮;此时便能出来"清空缓存并硬性重新加载"的选项了;如图:另外,可以如果只需要"硬性重新加载", 则直接快捷键Ctrl+Shift+R ;...

拓扑排序:如何确定代码源文件的编译依赖关系_鸭梨山大哎的博客-程序员信息网_编译依赖关系

什么是拓扑排序?由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序拓扑排序有何应用?我们知道,一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候,需要按照依赖关系,依次编译每个源文件。比如,A.cpp 依赖 B.cpp,那在编译的时候,编译器需要先编译 B.cpp,才能编译 A.cpp。编译器通过分析源文件或者程序员事先写好的编译配置文件(比如 Makefile 文件),来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系,确定一个全局的编

srs的http API控制相关接口_小狒猴宝宝的博客-程序员信息网_srs api

方法:查询到用户编号,即cid,然后调用delete。查询所有流curl -v -X GET http://10.1.0.222:1985/api/v1/streams/{"code":0,"server":24418,"streams":[{"id":24420,"name":"123","vhost":24419,"app":"live","live_ms":1532057...

随便推点

使用uni-app的框架进行图片或视频的(项目需求可能还有其它非图片和视频的文件,比如ppt的上传)上传_小也同学的博客-程序员信息网

思路第一步用uni.chooseImage或 uni.chooseMedia选取图片或视频,成功返回选中的图片或视频的参数信息,包括图片展示的路径(也就是本地图片的路径)、图片大小、图片格式等信息。第二步拿到本地的图片或视频的信息之后先用后台提供的上传文件的接口,对接接口之后会返回服务器(也就是线上不是本地的图片信息了)上存在的图片或视频的信息(就可以直接在浏览器输入展示图片或视频了)注意点uni-app有专门上传文件的api(uni.uploadFile)需要去看官网了解使用,其它不同的框架估

使用flume将kafka数据sink到HBase_专注于大数据技术栈的博客-程序员信息网

1. hbase sink介绍如果还不了解flume请查看我写的其他flume下的博客。接下来的内容主要来自flume官方文档的学习。顺便也强烈推荐flume 1.6 官方APIhbase的sink主要有以下两种。两种方式都提供和HBASE一样的一致性保证,即行级原子性1.1 HbaseSinkagent的配置时提供两种序列化模式:SimpleHbaseEventSer...

keras报错:ValueError: Negative dimension size caused by subtracting 5 from 1_小王做笔记的博客-程序员信息网

ValueError: Negative dimension size caused by subtracting 5 from 1报错现象任务背景问题参考问题解决解决呈现原始错误程序方式1 + 方式2 (结合使用)方式3报错现象ValueError: Negative dimension size caused by subtracting 5 from 1 for '{{node conv1d_8/conv1d}} = Conv2D[T=DT_FLOAT, data_format="NHWC"

kafka开启Kerberos安全认证Java编程生成者与消费组示例_聆听金生的博客-程序员信息网

一、相关配置文件kafka_client_jaas.conf配置项KafkaClient { com.sun.security.auth.module.Krb5LoginModule required useKeyTab=true storeKey=true keyTab="D:\\kafka-connect\\5.5.0\\kafka-schema-test\\src\\main\\resources\\test.service.keytab" useTic

HttpContext.Current.Request.Files后台取不到值的解决方法_coast0824的博客-程序员信息网_system.web.httpcontext.current.request.files 获取不到数

前台是3个INPUT:    在后台遍历 HttpFileCollection   files     =   HttpContext.Current.Request.Files; int   mm   =   files.Count;结果:mm   =0;可能有几种原因,针对这些原因有如下方法:一、form   的enctype不对.

东方程序员怎么看西方程序员_shd377143934的博客-程序员信息网

东方程序员怎么看西方程序员http://www.csdn.net/article/2012-09-20/2810169/1摘要:东方程序员与西方程序员,彼此心中是什么样子呢?本文收集了东西方程序员对彼此的看法与各种印象,对于西方/东方程序员,你留有什么印象呢?本文是作者根据StackExchange上的一个讨论贴:东方程序员眼中的西方程序员是怎样的?整理

推荐文章

热门文章

相关标签