精华内容
下载资源
问答
  • 给定一颗二叉树,以及其中的两个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)。

    展开全文
  • 235. Lowest Common Ancestor of a Binary Search Tree 235. Lowest Common Ancestor of a...如果大于最大值,则所求在左子树,如果小于最小值,则所求在右子树,否则,返回当前节点 # Definition for a bina...
        

    235. Lowest Common Ancestor of a Binary Search Tree

    17368230-8048f67b3f9678df.png
    235. Lowest Common Ancestor of a Binary Search Tree
    • 如果大于最大值,则所求在左子树,如果小于最小值,则所求在右子树,否则,返回当前节点
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        #循环
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            while root:
                if root.val > max(p.val, q.val):
                    root = root.left
                elif root.val < min(p.val, q.val):
                    root = root.right
                else:
                    return root
    
        #递归
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            if root.val > max(p.val, q.val):
                return self.lowestCommonAncestor(root.left, p, q)
            elif root.val < min(p.val, q.val):
                return self.lowestCommonAncestor(root.right, p, q)
            else:
                return root
    
        #找路径后比较
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            l1 = self.findPath(root, p)
            l2 = self.findPath(root, q)
            res = root
            for i in range(min(len(l1), len(l2))):
                if l1[i] == l2[I]:
                    res = l1[I]
                else:
                    break
            return res
        
        def findPath(self, root, p):
            res = []
            while root.val != p.val:
                res.append(root)
                if root.val > p.val:
                    root = root.left
                else:
                    root = root.right
            res.append(p)
            return res
    

    236. Lowest Common Ancestor of a Binary Tree

    17368230-8e4bbf631fb37a5b.png
    236. Lowest Common Ancestor of a Binary Tree
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            mydic = {}
            l1 = self.findPath(root, p)
            l2 = self.findPath(root, q)
            res = root
            for i in range(min(len(l1), len(l2))):
                if l1[i] == l2[I]:
                    res = l1[I]
                else:
                    break
            return res
    
        def findPath(self, root, p):
            res = []
            mydic = {}
            qu = [root]
            while qu:
                node = qu.pop(0)
                if node == p:
                    break
                else:
                    if node.left:
                        qu.append(node.left)
                        mydic[node.left] = node
                    if node.right:
                        qu.append(node.right)
                        mydic[node.right] = node
            while node != root:
                res.append(node)
                node = mydic[node]
            res.append(root)
            return res[::-1]
    
    展开全文
  • 二叉树中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);

                }

               }

     }

           

    展开全文
  • 二叉树之最小公共父节点

    千次阅读 2013-10-15 20:36:35
      import java.util.LinkedList;   public class CommonFather { ... * 思路:最原始的方法,从根开始,分别寻找从根节点到每个目标节点的路径,然后比较 两条路径,找到最小的公共父节点。  *

    package com.Tree;

     

    import java.util.LinkedList;

     

    public class CommonFather {

     

      /**

       * 题目描述:给定一棵二叉树,要求找到其中任意两节点的最小公共父节点。

       * 思路:最原始的方法,从根开始,分别寻找从根节点到每个目标节点的路径,然后比较 两条路径,找到最小的公共父节点。

       * @param args

       * @author Adai

       */

      private LinkedList<TNode> path;

      private static class TNode{

         int data;

          TNode leftchild;

          TNode rightchild;

         public TNode(int da){

            this.data=da;

            this.leftchild=null;

            this.rightchild=null;

          }

       }

      private TNode root;

      public CommonFather(int[] list){

          TNode curr=null;

         for(int i=0;i<list.length;i++){

             TNode now=new TNode(list[i]);

            if(i==0){

               root=now;

                curr=root;

             }else{

                curr=root;

               while(curr!=null){

                   if(curr.data<now.data){

                      if(curr.rightchild!=null){

                          curr=curr.rightchild;

                       }else{

                          curr.rightchild=now;

                         break;

                       }

                    }else{

                      if(curr.leftchild!=null){

                          curr=curr.leftchild;

                       }else{

                          curr.leftchild=now;

                         break;

                       }

                      

                    }

                }

               

             }

          }

       }

      public static void main(String[] args) {

         // TODO Auto-generated method stub

         int[] list={5,4,6,3,7,2,8,1,9};

          CommonFather cf=new CommonFather(list);

          TNode tar=cf.FindCommonFather(cf.root, 3, 7);

          System.out.println(tar.data);

       }

      public TNode FindCommonFather(TNode root,int t1,int t2){

         if(root==nullreturn null;

         path=new LinkedList<TNode>();

          LinkedList<TNode> set=new LinkedList<TNode>();

          TNode cur=root;

         if(FindTNode(cur,t1)){

            

            while(!path.isEmpty()){

                TNode now=path.pop();

                set.push(now); 

                System.out.println(now.data);

             }

          }else{

            return null;

          }

         path.clear();

          cur=root;

          LinkedList<TNode> guest=new LinkedList<TNode>();

         if(FindTNode(cur,t2)){

             TNode cf=null;

            while(!path.isEmpty()){

                TNode now=path.pop();

                System.out.println("2:"+now.data);

                guest.push(now);

             }

          }else{

            return null;

          }

          TNode ret=null;

         while(!set.isEmpty()&&!guest.isEmpty()){

             TNode se=set.pop();

             TNode ge=guest.pop();

            if(se.equals(ge)){

                ret=se;

             }else{

               return ret;

             }

          }

         return null;

       }

      

      private boolean FindTNode(TNode nowroot,int target){

         path.push(nowroot);

         if(nowroot==null){

            path.pop();

            return false;

          }else if(nowroot.data==target){

            return true;

          }else{

            if(FindTNode(nowroot.leftchild,target)){

               return true;

             }

            if(FindTNode(nowroot.rightchild,target)){

               return true;

             }

            path.pop();

            return false;

          }

       }

    }

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

    千次阅读 2015-07-19 10:37:22
    有一个普通二叉树,AB分别为两个子节点,求AB最近(深度最浅)的公共父节点。 此题仍然是一个老题,有着多种解决方法,本文针对其中三种方法来进行分析总结。 这三种方法分别是:递归法,tarjan离线算法,RMQ在线...
  •  两个节点的最小公共父节点;二是节点在同一侧,则 r->left 或者 r->right 为 NULL,另一边返回p或者q,  那么另一边返回的就是他们的最小公共父节点。 递归有两个出口,一是没有找到p或者q,则返回NULL;...
  • Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点 的Follow Up。跟之前那题不同的地方是,这道题是普通是二叉树,不是二叉搜索树,所以就不能利用其特有的性质,所以我们只能在二叉树中...
  • /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; ...clas
  • LCA最小公共父节点解法: 1、二叉搜索树: 中序遍历是升序,前序遍历即按序插入建树的序列。 二叉搜索树建树最好用前序+中序,如果用前序建树,最坏情况会退化为线性表,超时。 最近公共祖先甲级: A1143,1151 利用...
  • #include #include #include #include #include using namespace std; struct TreeNode{ char value; TreeNode * lchild; ... TreeNode(char val, TreeNode *lch, TreeNode * rch) :value(v
  • 查找二叉树中x和y的最小公共父节点。 代码实现:见我的github:findxandy 二、解题思路 1)写一个查找函数 findx:查找x是否在树2root中。 2)查找 root 的左孩子是否有该结点,递归。 3)查找 root ...
  • 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点...
  • 现在的问题就是,给定x和y,要求他们的公共父节点,即xi(也就是 yj)。 实现 import java.util.Scanner; public class Main { public static void main (String[] args) { Scanner input= new...
  • 采用递归,深度优先遍历,找到一个节点时,返回,逐层记录遍历方向,另一个节点 同,这样深度优先遍历后,可以找到这两个节点由根节点访问的路径,然后沿着这个 路径找到分叉的地方就行了 代码: #include<...
  • Lowest Common Ancestor of a Binary Tree 二叉树的最小共同父节点   Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition ...
  • 根元素是最小的元素,父节点小于它的两个子节点。树中的元素是相对有序的。如何实现堆的相对有序是关键。插入元素时,插入到数组中的最后一个元素的后面,然后与该节点的父节点比较大小。如果插入的元素小于父节点...
  • 题意: ...输入N行父子关系(题中为母女)即两个名字,前者是,后者是子; 问两只牛是什么亲属关系。 具体的输出规则(亲属关系)请见原题。 示例: Input: 7 AA ...
  • 为了找一个节点,binary search tree, 有左子树节点 右子树节点这样的规则。 可以利用二分查找来找到节点。 但这里是binary tree。如果找到我们的目标节点呢? 用遍历的方法!这是一种暴力的直接求解的办法。
  • 给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数...
  • 查找子节点的父节点 节点删除 销毁 关于删除节点的详细说明 删除节点比较复杂所以我们进行强调: 删除节点我们分为三种情况来处理: 代码实现: BST.cpp /* 搜索二叉树的节点增加和删除。 第一种情况: 若为叶子...
  • 按照二叉树的性质遍历即可 #include using namespace std; struct TreeNode { int val; TreeNode lChild; TreeNode rChild;...TreeNode(int val, TreeNodel = nullptr, TreeNoder = nullptr) ...l...
  • 如果是2叉树,那又如何编程? 以下是个人代码,调试通过并有注释 /*   *  * Author: Bigtree  *  * Created on  */  #include  #include  #include  #include ...long int NodesPerL
  • 如果根节点小于p和q之间的较小值,说明p和q都在右子树中,那么此时我们就进入根节点的右子节点继续递归,如果都不是,则说明当前根节点就是最小共同父节点,直接返回即可,参见代码如下: class Solution { ...
  • 若 root 有左右子结点,说明左右子树存在,通常情况下我们会对左右子结点调用递归,那么返回的就是左右子树分别的最深叶结点的最小公共父节点,但是问题来了,就算分别知道了左右子树的最深结点的 LCA,怎么推出当前...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,044
精华内容 1,217
关键字:

最小父节点