美文网首页
2017/05/15 二叉树

2017/05/15 二叉树

作者: 进击的NickMao | 来源:发表于2017-05-15 01:23 被阅读18次

题目

  1. 输入二叉树中的两个结点,输出这两个结点在树中最低的共同父结点
  2. 二叉树中两个节点的距离

分析

  1. 还是递归吧:
    思路: 如果这两个节点不在同一个子树下面,那么这棵树的根节点就是他们的共同最低父节点。
    如果两个都在右子树,那么以右子树的最上面的那个节点作为根节点,重新进行判断,递归调用。
    同理两个都在左子树,则方法同上。 也就是说,最终的结果分别只有三种情况,一个节点在右子树,一个节点在左子树。两个节点都在右子树,两个节点都在左子树。
    如果是第一种情况,那么当前的节点就是他们最低的公共节点,左右都在左子树,或者在右子树,那么就递归调用。
    那么问题就变成了如何判断是否在同一子树。

相关文章

  • 开始

    今天我开通了简书,2017/05/15.

  • css杂记

    title: css杂记date: 2017-05-21 15:52:05tags: css笔记 word-spa...

  • 随笔 - 草稿

    2017年04月05日 2017-04-05 15:59阅读:10 清明时节雨纷飞。 今年的清明,也就是昨天,雨、...

  • 2017/05/15 二叉树

    题目 输入二叉树中的两个结点,输出这两个结点在树中最低的共同父结点 二叉树中两个节点的距离 分析 还是递归吧:思路...

  • JVM工具_jcmd

    title: jvm工具_jcmddate: 2017-02-15 09:18:05tags:category: ...

  • 安全-中间人攻击MIMTF框架

    title: 安装MIMTf 框架tags: [安全, yunpiao]date: 2017-05-11 15:4...

  • tacacs授权流程

    报文信息 认证时授权:2017/05/15 11:18:35 [192.168.6.87:14404] Autho...

  • 与肥胖战斗三个月-—-D29

    2017-03-05 晴朗 呆家 排 【早餐】10:03 苹果 【午餐】12:15 面➕青菜 【晚餐】19:15 肉饭菜

  • spark报错

    2017-07-20 15:05:12 [task-result-getter-1] WARN org.apac...

  • IntelliJ Idea、Charles、Axure 激活免费

    title: IntelliJ Idea 免费激活方法date: 2017-05-15 23:23:57 一、In...

网友评论

      本文标题:2017/05/15 二叉树

      本文链接:https://www.haomeiwen.com/subject/xhpcxxtx.html