精华内容
下载资源
问答
  • 最小父节点
    2017-08-21 22:38:22

    题目:

    1
    / \
    2 3
    / \ / \
    4 5 6 7
    /\ /\ /\ /\
    如上图所示,由正整数 1, 2, 3, …组成了一棵无限大的二叉树。从某一个结点到根结点(编号是1的结点)都有一条唯一的路径,比如从5到根结点的路径是(5, 2, 1),从4到根结点的路径是(4, 2, 1),从根结点1到根结点的路径上只包含一个结点1,因此路径就是(1)。对于两个结点x和y,假设他们到根结点的路径分别是(x1, x2, … ,1)和(y1, y2,…,1),那么必然存在两个正整数i和j,使得从xi 和yj 开始,有xi = yj,xi + 1 = yj + 1,xi + 2 = yj + 2,…
    现在的问题就是,给定x和y,要求他们的公共父节点,即xi(也就是 yj)。

    实现

    import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner input=new Scanner(System.in);
            int a=input.nextInt();
            int b=input.nextInt();
            if(a>b){
                while(a!=b){
                    if(a>b){
                        a=a/2;
                    }
                    else{
                        b=b/2;
                    }
                }
                System.out.println(a);
            }
            else if(a<b){
                while(a!=b){
                    if(a>b){
                        a=a/2;
                    }
                    else{
                        b=b/2;
                    }
                }
                System.out.println(a);
            }
            else{
                System.out.println(a);
            }
        }
    }
    更多相关内容
  • 给定一颗二叉树和两个任意节点,请求解出这两个节点的最小公共父节点,如果其中一个节点本身是另外一个的父类,那么就返回这个父节点,否则,就返回距离他们俩最近的公共父节点。此题给定的两个节点肯定在这颗二叉树...

    题目描述

    给定一颗二叉树和两个任意节点,请求解出这两个节点的最小公共父节点,如果其中一个节点本身是另外一个的父类,那么就返回这个父节点,否则,就返回距离他们俩最近的公共父节点。此题给定的两个节点肯定在这颗二叉树中。

    思路分析

    常规思路,二叉树只能从父节点到孩子节点遍历,从孩子节点往上回溯比较困难,因此,此题既然要求求出最小公共父节点,那么,就构造一个从孩子节点回溯父节点的数据结构,用map保存孩子节点对应的父节点。
    然后,从给定的两个节点中的任意一个开始向上回溯父节点,将路径上的所有节点都放入set中,然后,再回溯另一个,每遍历到一个父节点就在set中查找是否存在,返回找到的第一个节点,就是最小公共父节点。

    代码

    public static Node get(Node head,Node n1,Node n2){
            HashMap<Node,Node> map=new HashMap<>();
            map.put(head,head);
            getMap(map,head);
            HashSet<Node> set=new HashSet<>();
            while (n1!=head){
                set.add(n1);
                n1=map.get(n1);
            }
            set.add(head);
            while (true){
                if(set.contains(n2)){
                    return n2;
                }else {
                    n2=map.get(n2);
                }
            }
        }
    
        private static void getMap(HashMap map,Node node) {
            if(node==null){
                return;
            }
            Node left=node.left;
            Node right=node.right;
            if(left!=null){
                map.put(left,node);
            }
            if(right!=null){
                map.put(right,node);
            }
            getMap(map,left);
            getMap(map,right);
        }
    

    思路二

    总体思路是想利用递归向上返回的值来返回最小公共父节点。
    分析题目的两种情况:
    情况一:n1或者n2本身是另一个的父类节点,那么,最终结果应该是这个父节点本身。因此,向上返回的数据,返回它本身就可以了,如果它下面有另一个,也返回它自己本身就行,这样就会把下面的覆盖掉。然后,其余节点,如果不是n1和n2,就返回null,如果接收的返回值包含n1或者n2,就继续向上传递。
    情况二:n1和n2本身没有父子关系,他们有一个公共的父节点,那么,向上传递的信息,n1或者n2就传递他们本身,但是,和上面有一点不同的地方在于,其余节点,有可能接收的返回值包含n1和n2两个,那么,其实这个节点就是最小的公共父类节点,因此,如果接收的左右孩子分别为n1和n2,那么,就返回他自己本身。其余节点还是接收什么就原样向上返回。
    因此,总结一下上面分析的结果,向上返回的数据:
    本身为n1或者n2,就向上返回自己
    接收两个的话,就返回自己
    如果接收一个,就原样照抄返回
    自己不是n1和n2,且没有接收,就返回null

    代码

        public static Node getFather(Node node,Node n1,Node n2){
            if(node==null||node==n1||node==n2){
                return node;
            }
            Node left=getFather(node.left,n1,n2);
            Node right=getFather(node.right,n1,n2);
            if(left!=null&&right!=null){
                return node;
            }
            return left!=null ? left:right;
        }
    
    展开全文
  • 二叉树中2个节点的最小公共父节点

    千次阅读 2017-01-19 15:17:03
    关于如何求二叉树2个节点的最小公共父节点,分2种情况讨论 情况1:节点有parent节点  这种情况就直接找到节点1和节点2的根节点,然后求得2个链表的长度,再求得长度差。如果说2条链子的长度差为n,那么  就长的...

    关于如何求二叉树2个节点的最小公共父节点,分2种情况讨论

    情况1:节点有parent节点

               这种情况就直接找到节点1和节点2的根节点,然后求得2个链表的长度,再求得长度差。如果说2条链子的长度差为n,那么

     就长的节点先移动n步,然后和短的节点一起移动,并且判断父节点是否相等。那么这边其实也解决了另一个问题,就是求2个链表

     的交点。

                public static Node publicNode(Node node1,Node node2){

                //接下来是求2个条链的起始点

                int length1 = getLength(node1);

                int length2 = getLength(node2);

               Node firstNode,secondNode;

                int res = 0;

                if(length1>=length2)

                res = length1 - length2;

                for(int i = 0;i<res;i++){

                firstNode = firstNode.parent;

                }

                else{

                res = length2 - length1;

                for(int i = 0;i<res;i++){

                secondNode = secondNode.parent;

                }

              // 接下来是从起始节点开始找交点

               while(firstNode.parent!=null||secondNode.parent!=null){

                          if(node1.parent==node2.parent)

                          return node1.parent;

                          else{

                             firstNode = firstNode.parent;

                             secondNode = secondNode.parent;

                          }

               }

               }

           其实会这么一个问题,就会求链表的交点和求二叉树的2个节点的最小公共父节点了。

      情况2,节点没有parent节点

      这个其实也简单,就是从根节点开始层次遍历这棵树,然后判断当前节点是否包含2个节点,如果包含就继续遍历当前节点的

      左右节点是否包含这2个节点,如果包含就继续深入。如果左右都不包含,那么当前节点就是最小公共父节点。

      public static Node getPublicNode(Node node1,Node node2){

                //获得根节点,并且对根节点进行层次遍历

                Node root = getRoot(node1);

                Deque<Node> deque = new Deque<Node>();

                deque.add(root);

                while(deque.size()!=0){

                Node node = deque.peekFirst();

                if(node.containChilds(node1,node2)){

                 //当当前节点包含2个节点,而它的左右节点都不包含2个节点,那么它就是最小公共父节点

                if(node.left!=null&&node.right!=null&&!node.right.containChilds&&!node.left.containChilds){

                 return node;

                 }

                if(node.left!=null&&node.left.containChilds(node1,node2))

                deque.add(node.left);

               if(node.right!=null&&node.right.containChilds(node1,node2))

                deque.add(node.right);

                }

               }

     }

           

    展开全文
  • 给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数...
    给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数原型:
    C++函数原型:
    strucy TreeNode{
         TreeNode* left;   //指向左子树
         TreeNode* right;   //指向右子树
         TreeNode* father;   //指向父亲节点
    };
    TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
    }


    思路一:我们首先找到两个节点的高度差,然后从较靠近根结点的一层开始向上找,若父节点为同一节点则该节点为解。
    intgetHeight(TreeNode *node) {
        intheight = 0;
        while(node) {
            height++;
            node = node->parent;
        }
        returnheight;
    }
     
    TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {
        intheight1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;
        if(diff < 0) {
            diff = -diff;
            while(diff--) {
                 second = second->parent;
            }
        } else{
            while(diff--) {
                first = first->parent;
            }
        }
        while(first != second) {
            first = first->parent;
            second = second->parent;
        }
        returnfirst;
    }
    

    思路二:若允许浪费空间,那么可以用两个Stack来存储从first和second到根结点的各个节点,然后出栈时比较地址是否一致,最后一个地址一致的节点为解。

    两种方法最坏时间复杂度均为O(n)。

    展开全文
  • LCA-最小公共父节点

    千次阅读 2015-07-19 10:37:22
    有一个普通二叉树,AB分别为两个子节点,求AB最近(深度最浅)的公共父节点。 此题仍然是一个老题,有着多种解决方法,本文针对其中三种方法来进行分析总结。 这三种方法分别是:递归法,tarjan离线算法,RMQ在线...
  • 查找二叉树中x和y的最小公共父节点

    千次阅读 2018-08-31 22:04:52
    查找二叉树中x和y的最小公共父节点。 代码实现:见我的github:findxandy 二、解题思路 1)写一个查找函数 findx:查找x是否在树2root中。 2)查找 root 的左孩子是否有该结点,递归。 3)查找 root ...
  • leetcode 236 二叉树的最小共同父节点

    千次阅读 2018-12-04 12:54:05
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点...
  • 二叉树之最小公共父节点

    千次阅读 2013-10-15 20:36:35
      import java.util.LinkedList;   public class CommonFather { ... * 思路:最原始的方法,从根开始,分别寻找从根节点到每个目标节点的路径,然后比较 两条路径,找到最小的公共父节点。  *
  • 描述: 以数组来存储二叉树,现给定一个数组 树的根节点的值储存在下标1, 对于储存在下标n的节点, 他的左子节点和右子节点...将给定的数组先转换为二叉树,转换时添加一个向上的parent指针指向父节点 2.层序遍历所...
  • 这个问题可以分为四种情况来考虑: ...此时可以分别从两个节点开始,沿着parent指针走向根节点,得到两个链表,然后求两个链表的第一个公共节点,这个方法很简单,不需要详细解释的。 情况二:节点只有左、右指针,没
  • 二叉树求最大最小叶子节点距离

    千次阅读 2019-09-18 11:48:52
    有一棵二叉树,树上每个点标有权值,权值各不相同,请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1,一个节点经过多少条边到达另一个节点为这两个节点之间的距离。 给定...
  • 给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数...
  • if( findflag1 == true && findflag2 == true){//在两个遍历路径上查找最后一个相同的节点,就是最低公共祖先节点(最近公共父节点) vector*> ::iterator iter1 = vec1.begin(); vector*> ::iterator iter2 = ...
  • 三叉树与二叉树很像,但是每个父节点有三个子节点,而不是两个子节点-左节点的值小于父节点,右节点的值大于父节点,中间节点的值等于给父母。 ###功能:### 插入节点2.删除节点3.查找最小节点4.将树转换为字符串...
  • 思路:有两种情况,一是要找的这两个节点(a, b),在要遍历的节点(root)的两侧,那么这个节点就是这两个节点的最近公共父节点; 二是两个节点在同一侧,则 root->left 或者 root->right 为 NULL,另一边返回a或者...
  • 最小高度的盒子里面的子元素不能继承高度 现象:对元素使用 min-height 为 300px,在子元素不脱离文档流的情况下,对子元素设置为 30%,但实际显示的时候,子元素的 height 是 0。 当你让一个元素的高度设定为...
  • 最小堆排序的实现(Go)

    2021-01-07 20:06:07
    最小堆的特点是其父节点的值不大于任何一个字节点的值, 实现的是升序排序。 最小堆实现排序的原理,构建一个堆,不断的删除堆顶,这里的删除并不是完全删除, 而是将堆顶移动到末尾,然后父节点开始下沉操作,最后...
  • 昨天接到阿里的电话面试,其中有一道题便是这个。当时这个问题我回答的不好,因为我不明白为什么要问这道题。...思路:获取到元素下的所有孩子节点后,从后往前遍历循环,整合获取到每个子元素的oute
  • 二叉查找树 - 删除节点 详解(Java实现)

    万次阅读 多人点赞 2018-05-17 12:18:31
    //如果当前节点没有父节点(后继情况到这儿时一定有父节点) //说明要删除的就是根节点 if (node.parent == null ) //根节点设置为子节点 //按照前面逻辑,根只有一个或者没有节点,所以直接赋值 child...
  • 二、贪婪准则:从所有边中依次选出权值最小的边,加入图中,还必须保证新加入的边不会产生环路,若产生环路,则抛弃 三、加到n-1条边,则结束循环,就会生成该图的最小生成树 伪代码如下: 现在的问题就是...
  • 最小

    千次阅读 2020-10-16 10:45:05
    一、 满二叉树 一个深度为k,节点个数为2^k-1的二叉树为满二叉树,即一棵树深度为k,没有空位。...最小堆是一种经过排序的完全二叉树,其中任意非终端节点数值均不大于其左子节点和右子节点的值。 如果一棵..
  • 本文实例讲述了layui框架中layer父子页面交互的方法。分享给大家供大家参考,具体...当layer以iframe层的方式弹出新的窗口(子页面),如何在子页面中访问页面的元素和函数。1、访问页面元素值var parentId=parent...
  • 数据结构之最小

    千次阅读 2022-05-18 22:04:31
    最小堆可以看作是一种优先级队列的实现,有些应用场景需要从队列中获取最小的或者最大的元素,而且不要求数据全部有序,使用最小堆或者最大堆能很好的解决这类问题。...当i为0时,表示树的根节点,没有父节点; 节点
  • //获取右子树中的最小节点 public Node minRightNode(Node node){//传入参数为被删除节点的右孩子Node node if(node.getLeftChild()==null){ return null; } if(node.getLeftChild().getLeftChild()==null...
  • 并且用一个一维数据记录节点的父节点,出队列的同时判断两个点的父节点是否相同,同则不用,不同则可以用。判断是不是树的时候,可以根据根节点判断,因为每个节点中存储的父节点都会间接指向根节点。Kruskal算法...
  • Python - 最小堆实现与应用

    千次阅读 2021-12-04 10:00:13
    最小堆,又称小根堆(小顶堆)是指根节点(亦称为堆顶)的值是堆里所有节点值中的最小
  • 寻找二叉树两个结点的最低共同父节点1.使用递归的思想(从根节点自上向下查找,优点直观易懂,缺点使用较大内存);2.使用迭代的思想(从两目标节点自下向上查找,缺点运行较长时间,改进:可以牺牲内存记录找过的节点...
  • 问题 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足...首先根节点肯定是二者的父节点,题目是去

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 122,187
精华内容 48,874
关键字:

最小父节点