精华内容
下载资源
问答
  • 的编程平时基本没怎么用到,花功夫去专门研究的人不多,所以笔试面试出的情况比较... 二叉树分为有序二叉树(也叫二叉搜索)和无序二叉树,对于有序二叉树,求节点的最低公共节点,只需要求比其中较小数大、较...

    树的编程平时基本没怎么用到,花功夫去专门研究的人不多,所以笔试面试出树的情况比较多,看了别人总结的,自己写一份,加深印象。

    参考博客:http://zhedahht.blog.163.com/blog/static/25411174201081263815813/

      二叉树分为有序二叉树(也叫二叉搜索树)和无序二叉树,对于有序二叉树,求节点的最低公共节点,只需要求比其中较小数大、较大数小的节点就可以了,用递归很容易就可以实现。但是对于无序二叉树,再用递归的话会浪费很多时间,会重复遍历,可以用空间换时间,用链表来记录从树节点到所求两个节点的路径,然后求出最后一个公共节点,这个公共节点就是最低公共节点。

    #include<iostream>
    #include <list>
    using namespace std;

    typedef struct treeNode
    {
    int data;
    treeNode* lchild;
    treeNode* rchild;
    }treeNode,*node;


    void createTree(node &t)//先序递归建立二叉树(例如输入:2100300)
    {
    int a;
    cin>>a;
    if(a==0)
    {
    t=NULL;
    }
    else
    {
    t=new treeNode;
    t->data=a;
    createTree(t->lchild);
    createTree(t->rchild);
    }
    }

    bool getNodeList(int t,node root,list<node> &pathlist)//从需要获取的节点得出路径
    {
    if(t==root->data)
    return true;
    pathlist.push_back(root);
    bool found=false;
    if(root->lchild!=NULL)
    found=getNodeList(t,root->lchild,pathlist);
    if(!found&&root->rchild!=NULL)
    {
    found=getNodeList(t,root->rchild,pathlist);
    }
    if(!found)
    pathlist.pop_back();
    return found;
    }

    得出的两个链表是以树节点为开始的两个链表,是一个倒立的"Y"型,只需要从两个链表的节点依次遍历直到不相等即可。
    node findLastCommon(list<node> pathlist1,list<node> pathlist2)
    {
    list<node>::iterator itor1=pathlist1.begin(),itor2=pathlist2.begin();
    int length1=0,length2=0;
    node plast;
    while(itor1!=pathlist1.end()&&itor2!=pathlist2.end())
    {
    if(*itor1==*itor2)
    plast=*itor1;
    itor1++;
    itor2++;
    }

    return plast;
    }

     


    void main()
    {
    node root;
    createTree(root);
    cout<<root->data<<endl;
    list<node> pathlist1,pathlist2;
    getNodeList(6,root,pathlist1);
    getNodeList(11,root,pathlist2);
    node t=findLastCommon(pathlist1,pathlist2);
    cout<<t->data;

     

    }

     

    转载于:https://www.cnblogs.com/gardener/p/6004174.html

    展开全文
  • 题目:求中两个结点的最低公共祖先,此不是二叉树,并且没有指向父节点的指针。 基本思路 我们首先得到一条从根结点到中某一结点的路径,这就要求在遍历的时候,有一个辅助内存来保存路径. 比如我们用...

    题目:求树中两个结点的最低公共祖先,此树不是二叉树,并且没有指向父节点的指针。

    基本思路

    我们首先得到一条从根结点到树中某一结点的路径,这就要求在遍历的时候,有一个辅助内存来保存路径.

    比如我们用前序遍历的方法来得到从根结点到H 的路径的过程是这样的:( 1 )遍历到A,把A 存放到路径中去,路径中只有一个结点A; ( 2 )遍历到B,把B 存到路径中去,此时路径为A->B; ( 3 )遍历到D,把D 存放到路径中去,此,时路径为A->B->D; ( 4 ) 遍历到F,把F 存放到路径中去,此时路径为A->B->D->F;( 5) F 已经没有子结点了,因此这条路径不可能到这结点H. 把F 从路径中删除,变成A->B->D; ( 6 )遍历G. 和结点F 一样,这条路径也不能到达H. 边历完G 之后,路径仍然是A->B->D; ( 7 )由于D 的所有子结点都遍历过了,不可能到这结点H,因此D 不在从A 到H 的路径中,把D 从路径中删除,变成A->B; ( 8 )遥历E,把E 加入到路径中,此时路径变成A->B->E, ( 9 )遍历H,已经到达目标给点, A->B->E 就是从根结点开始到达H 必须经过的路径。同样,我们也可以得到从根结点开始到达F 必须经过的路径是A->B。接着,我们求出这两个路径的最后公共结点,也就是B. B这个结点也是F 和H 的最低公共祖先.为了得到从根结点开始到输入的两个结点的两条路径,需要遍历两次树,每边历一次的时间复杂度是O(n)。

     Java实现:

    public class GetLastCommonParent {
    	 /**
         * 树的结点定义
         */
        private static class TreeNode {
            int val;
    
            List<TreeNode> children = new LinkedList<>();
    
    
            public TreeNode() {
            }
    
            public TreeNode(int val) {
                this.val = val;
            }
    
            @Override
            public String toString() {
                return val + "";
            }
        }
    
    	public static TreeNode getLastCommonParent(TreeNode root,TreeNode p1,TreeNode p2) {
    		List<TreeNode> path1 = new LinkedList<>();
            getNodePath(root, p1, path1);
            List<TreeNode> path2 = new LinkedList<>();
            getNodePath(root, p2, path2);
    		return getLastCommonNode(path1,path2);
    	}
    
    	//找两个路径中的最后一个共同的结点
    	private static TreeNode getLastCommonNode(List<TreeNode> path1, List<TreeNode> path2) {
    		// TODO Auto-generated method stub
    		Iterator<TreeNode>ite1=path1.iterator();
    		Iterator<TreeNode>ite2=path2.iterator();
    		TreeNode last=null;
    		while(ite1.hasNext()&&ite2.hasNext()) {
    			TreeNode temp=ite1.next();
    			if(temp==ite2.next()) {
    				last=temp;
    			}
    		}
    		return last;
    	}
    
    	//找结点的路径
    	private static void getNodePath(TreeNode root, TreeNode target, List<TreeNode> path) {
    		// TODO Auto-generated method stub
    		//终止递归
    		if(root==null)
    			return;
    		//t添加当前节点
    		path.add(root);
    		//处理子节点
    		for(TreeNode node:root.children) {
    			if(node==target) {
    				path.add(node);
    			}else {
    				getNodePath(node,target,path);
    			}
    		}
    		// 现场还原
    		path.remove(path.size()-1);
    	}
    }

     

    展开全文
  •  求树种任意两个节点的最低公共节点   常见的解法是求解节点到根的路径,对路径做比对。参见: http://gaotong1991.iteye.com/blog/2042770 下面来介绍另外一种方法求解。 准备: 1、什么是最低公共节点?...
    问题:
         求树种任意两个节点的最低公共节点
     

    常见的解法是求解节点到根的路径,对路径做比对。参见: http://gaotong1991.iteye.com/blog/2042770

    下面来介绍另外一种方法求解。
    准备:
    1、什么是最低公共节点?
     
    2、最低公共节点有哪些方面需要注意?
    答:按照两个节点是否存在一个节点(设为A)是以另外一个节点(设为B)为根的子树中,分为两种情况:
        意味着A和B在B的一个分支下,返回B即可。
        意味着A和B肯定在公共节点的不同分支下,可以按下文的2、3、4步骤处理。
    3、如何判断两个节点是否存在一个节点(设为A)是另外一个节点(设为B)的(直接或间接)孩子?
    答:如果两个节点在树的前序和后续遍历中出现的顺序相反,则说明存在;反之,不存在。
     
    示例数据:


     
    测试用例:
         F/H-->B;B/F-->B
    步骤:
    1、分别输出树的前序(ABDFGEHIJC)和后续遍历结果(FGDHIJEBCA);
    2、如果F、H在前序和后续中的出现顺序相反,则说明F、H存在一个节点在另外一个节点的子树中的情况(例如选择的节点是B和F,F位于以B为根子树中),直接返回前序遍历中较早出现的一个节点,程序退出
    3、对前序遍历结果求出两个节点(F,H)前面的公共节点数组(按正序排列),记为M(ABD)
    4、对后续遍历结果求出两个节点(F,H)后面的公共节点(按逆序排列),记为N(ACBEJI)
    5、求MN的最大公共子序列K(AB),K的最后一个元素B就是最低公共祖先,程序退出
    特点:
    1、前序遍历和后续遍历的结果对于任何两个节点而言都是可用的,意味着不管是对哪两个节点来说,都可以使用遍历的结果;
    2、将非线性问题转换为线性问题——最大公共子序列。
    展开全文
  • 给定一个二叉搜索, 找到该中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个...

    剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

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

    例如,给定如下二叉搜索树:
    测试用例① root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    测试用例② root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4


    思路1:递归

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root==nullptr || p==nullptr || q==nullptr)
                return nullptr;
            if(root->val > p->val && root->val > q->val){  
                root = lowestCommonAncestor(root->left,p,q);
            }else if(root->val < p->val && root->val < q->val){
                root = lowestCommonAncestor(root->right,p,q);
            }
    
            return root;   //p,q分别在root左右两边;p==root;q==root
        }
    };
    

    思路2:迭代

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root==nullptr || p==nullptr || q==nullptr)
                return nullptr;
    
            while(root!=nullptr){
                if(root->val > p->val && root->val > q->val){  
                    root = root->left;
                }else if(root->val < p->val && root->val < q->val){
                    root = root->right;
                }else
                    break;
            }
    
            return root;   //p,q分别在root左右两边;p==root;q==root
        }
    };
    

    剑指 Offer 68 - II. 二叉树的最近公共祖先
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root==nullptr || p==nullptr || q==nullptr)
                return nullptr;
    
            list<TreeNode*> path1;
            getNodePath(root,p,path1);
    
            list<TreeNode*> path2;
            getNodePath(root,q,path2);
            
            return getLowestCommonNode(path1,path2);
        }
    
        bool getNodePath(TreeNode* root, TreeNode* node, list<TreeNode*>& path){
            path.push_back(root);
    
            if(root==node)
                return true;
    
            bool found=false;
            if(!found && root->left!=nullptr)
                found=getNodePath(root->left,node,path);
            if(!found && root->right!=nullptr)
                found=getNodePath(root->right,node,path);
    
            if(!found)
                path.pop_back();
    
            return found;
        }
    
        TreeNode* getLowestCommonNode(const list<TreeNode*>& path1, const list<TreeNode*>& path2){
            TreeNode* pLowest = nullptr;
    
            list<TreeNode*>::const_iterator i1=path1.begin();
            list<TreeNode*>::const_iterator i2=path2.begin();
            while(i1 != path1.end() && i2 != path2.end()){
                if(*i1 == *i2)
                    pLowest=*i1;
    
                i1++;
                i2++;
            }
            return pLowest;
        }
    };
    
    展开全文
  • 题目:给出两个结点A和B,...所以我们求两个节点最低公共节点应满足(父节点大于其中一个节点且小于另外一个。)如果此时搜索的节点大于这两个节点,则最低父节点应在该节点的左子树中,相反的,此时搜索的节点
  • 最低公共祖先
  • 这个题目其实是具有二义性的,因为没有对的结构进行说明,例如二叉树搜索,具有指向父节点引用的,和普通的,针对三种情况对应的处理方式是不同的,接下来我们结合三种情况来具体分析一下:二叉搜索根据...
  • 思路1:最低公共节点满足这样的条件:两个节点分别位于其左子树和右子,那么定义两个bool变量,leftFlag和rightFlag,如果在左子树中,leftFlag为true,如果在右子中,rightFlag为true,仅当leftFlag == ...
  • 1. 是二叉搜索,二叉搜索的特点是根节点值大于所有左子树节点值,小于所有右子树节点值,则最低公共祖先即该节点值大于给定两个节点中的一个值,小于另外一个节点的值,go代码实现如下 type TreeNode struct...
  • 1.为二叉搜索,二叉搜索...b:若该节点值比所给两个节点均小,则公共祖先节点必在其右子上,遍历其右子。 c:直到找到一个节点,位于两节点的中间。 Given a binary search tree(BST),find the lowest comm
  • 剑指Offer(第二版)面试案例:中两个节点最低公共祖先节点 题目:输入两个树节点,求它们的最低公共祖先节点。 反问:这棵是不是二叉树? 面试官:是二叉树,并且是二叉搜索。 思路: 二叉搜索是...
  • 给定两个树节点,返回这两个节点最近的一个公共节点。二叉搜索struct BinaryTreeNode{ int val; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int num):val(num),left(NULL),right(NULL){}...
  • 题目描述:给定一个二叉搜索,输入两个节点,求中两个节点最低公共祖先 思路:从根节点开始遍历,如果节点 p 和 q 都在右子上,那么以右孩子为根节点递归,如果节点 p 和节点 q 都在左子树上,那么以左...
  • 递归的解法如下: public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  if(root==null||root==p||root==q)  return root;  TreeNode left = lowestCommonAncestor(ro...
  • 为二叉排序,寻找给定两节点最低公共祖先 当为普通,每个节点中有指针指向其父节点为二叉树,每个节点仅有左右孩子指针 当为普通,每个节点仅有左右孩子指针 排序二叉树 排序二叉树...
  • 68. 中两个节点最低公共祖先 68.1 二叉查找 解题思路 在二叉查找中,两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。 public TreeNode lowestCommonAncestor...
  • 中两个节点最低公共祖先给定一棵和两个节点,求解这两个节点中的最低公共祖先节点。(剑指Offer)思路: 从根节点遍历,直到要查找的节点,保存从根节点到要查找的节点的路径。遍历两次,即保存了...
  • 中的两个节点最低公共祖先,是一组题目,不同条件下的题目是完全不一样的。情形1、二叉搜索分析:如果是二叉搜索的话,就比较容易解决。因为二叉搜索的特性,左子树的上节点的值比根节点小,右子上...
  • 题目描述:给定一个二叉搜索,输入两个节点,求中两个节点最低公共祖先思路:从根节点开始遍历,如果节点p 和q 都在右子上,那么以右孩子为根 节点递归,如果节点p 和节点q 都在左子树上,那么以左孩子为...
  • 上图中节点C、D的最低公共祖先为B; 节点B、E 的最低公共祖先为A; 节点D、F的最低公共最先为A; 其与的依次类推即可。 代码如下: BTNode* GetAncestorOfTwoNode(BTNode* pRoot, int nData1, int nData2) ...
  • 2、得到路径后,我们对两个路径进行比较,最后一个相等的节点即为所求(添加与取得顺序相反,所以最后一个为最低公共节点) public TreeNode getLastCommonParent(TreeNode root, TreeNode p1, Tr...
  • 输入两个树节点,求它们的最低公共祖先节点。 一、二叉搜索 应聘者:这棵是不是二叉树? 面试官:是二叉树,并且是二叉搜索。 思路: 二叉搜索是经过排序的,位于左子树的节点都比父...
  • (1)如果两个节点分别在根节点的左子树和右子,则返回根节点 (2)如果两个节点都在左子树,则递归处理左子树;如果两个节点都在右子,则递归处理右子 bool FindNode(BTree* pRoot, BTree* pNode) { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 403
精华内容 161
关键字:

最低公共节点树