`
薛定谔
  • 浏览: 22282 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

获取二叉树中两个节点的最近公共祖先

 
阅读更多

题目:获取一颗二叉树中任意两个节点的最近公共祖先

 

解答:

//二叉树节点对象
public class TreeNode{
    private TreeNode left = null;
    private TreeNode right = null;
    private int data = 0;

    public TreeNode  getLeft(){
        return left;
    }
    
    public TreeNode getRight(){
        return right;
    }

    public int getData(){
        return data;
    }
    
    //获取最近公共祖先
    public static TreeNode getNearestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null || p == null || q == null){
            return null;
        }else{
            if(contains(root.getLeft(), p)){
                if(contains(root.getRight(), q)){
                    return root;
                }else{
                    return getNearestCommonAncestor(root.getLeft(), p, q);
                }
            }else{
                if(contains(root.getRight(), q)){
                    return getNearestCommonAncestor(root.getRight(), p, q);
                }else{
                    return root;
                }
            }
        }
    }

    //给定的树root中是否包含节点p
    private static boolean contains(TreeNode root, TreeNode p){
        if(root.getData() == p.getData()){
            return true;
        }else{
            return contains(root.getLeft(), p) || contains(root.getRight(), p);
        }
    }
}

 

 

0
0
分享到:
评论

相关推荐

    面试题68 – II. 二叉树的最近公共祖先

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)” 例如,给定如下二叉树: root = [3...

    寻找二叉树两结点最近的祖先

    (1)拟定合适的二叉树的输入形式和构造算法; (2)能够以直观的形式观察所建立的二叉树的结构;

    二叉树的最近公共祖先II1

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

    floatLig#JavaLearning#236.二叉树的最近公共祖先1

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

    Easay#JavascriptCoding#剑指68-2.二叉树的最近公共祖先1

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

    Cygra#Leet-Code-Solus#0236. 二叉树的最近公共祖先1

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

    二叉树的相关操作

    本程序包括二叉树的一些常见的相关操作,比如非递归建立二叉树,二叉树的非递归遍历,非递归求二叉树的叶子数目,层数,任意两个节点的公共祖先,跟到叶子节点的所有路径,根据中序和后序的遍历结果建立二叉树等等。

    二叉树的各种操作源代码c++

    //求二叉树的节点个数//前序打印叶子节点//二叉树的遍历//求二叉树的第k层节点的值//交换二叉树的左右子树//求二叉树中两个节点的最低公共祖先节点//求双亲节点//判断两棵二叉树是否相同//二叉树删除节点//二叉树...

    第五章 树与二叉树

    由于二叉树中每个结点都可能有两个子树,因此需要寻找一条合适的搜索路径。 1、前序遍历 前序遍历二叉树操作定义为: 若树为空,则空操作返回;否则 (1)访问根结点 (2)前序遍历根结点的左子树 (3)前序遍历根...

    树的公共父节点.rar

    因为树的结构不同所以需要分情况...当树为二叉排序树,寻找给定两节点的最低公共祖先 当树为普通树,每个节点中有指针指向其父节点 当树为二叉树,每个节点仅有左右孩子指针 当树为普通树,每个节点仅有左右孩子指针

    common-father.rar_Father

    如何求二叉树的任意两个节点的公共祖先,可以通过编译

    二叉树家谱

    12.从文件中读出所有节点信息到一个数组中,然后按一年中生日的先后进 行快速排序。 13、按姓名查询家谱成员并显示该成员的各项信息。 14、给出某一成员的姓名,删除该成员和该成员的所有子孙。 15、成员信息的...

    最大公共字符串leetcode-Binary-Tree:Swift中的二叉树

    直径或宽度(树中任意两个节点之间的最长距离) 二叉树节点的组成部分 它保存的数据类型,例如Int或String等 指向左子节点的指针 指向右子节点的指针 常见操作 遍历 插入 删除 二叉树节点 class BinaryTreeNode <...

    二叉排序树与平衡二叉树的实现

     平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各...

    为面试做准备的python经典编程题之4

    在排序数组中查找数字.py 二叉搜索树的第k大节点.py 二叉树的深度.py 数组中数字出现的次数.py 和为s的数字.py 翻转字符串.py 队列的最大值.py n个骰子的点数.py ...树中两个节点的最低公共祖先.py

    《剑指Offer》题目及代码.zip

    50. 树中两个节点的最低公共祖先 51. 找出重复的数 52. 构建乘积数组 53. 正则表达式匹配 54. 表示数值的字符串 55. 字符流中第一个不重复的字符 56. 链表中环的入口节点 57. 删除链表中重复的节点 58. ...

    目前最火最热门的python经典编程题之3

    50.第一个只出现一次的字符 50.字符流中第一个不重复的字符 51.数组中的逆序对 Array 常考 52.两个链表的第一个公共结点 Linked List 53.数字在排序数组中出现的次数 ...68.树中两个节点的最低公共祖先 常考

    机器学习面试题答案1

    1. 一根木棒截成三段,能组成三角形的概率 2. · 找二叉树中任意两个节点的最近公共祖先 3. · 推导一下逻辑回归算法,如何得到 loss function

    problems:在 JavaScript 中解决的编程问题

    树木二叉搜索树验证从排序数组创建二叉搜索树为给定的二叉树创建每个深度的所有节点的链表在 BST 中按顺序查找节点的后继查找二叉树中两个节点的共同祖先返回二叉树中总和为给定值的所有路径检查二叉树是否平衡检查...

    leetcode跳跃-leetcoe:力扣刷题记录

    二叉树的最近公共祖先 路径总和II 打家劫舍III 没做出来。动态规划算法 二叉树的垂序遍历 删除二叉搜索树中的节点 移除链表元素 环形链表 回文链表 环形链表 II 两两交换链表中的节点 对...

Global site tag (gtag.js) - Google Analytics