江苏网站备案流程图,如何建广告网站,承德名城建设集团网站,24淘宝网站建设这个问题可以分为三种情况来考虑#xff1a;情况一#xff1a;root未知#xff0c;但是每个节点都有parent指针 此时可以分别从两个节点开始#xff0c;沿着parent指针走向根节点#xff0c;得到两个链表#xff0c;然后求两个链表的第一个公共节点#xff0c;这个方法很… 这个问题可以分为三种情况来考虑情况一root未知但是每个节点都有parent指针 此时可以分别从两个节点开始沿着parent指针走向根节点得到两个链表然后求两个链表的第一个公共节点这个方法很简单不需要详细解释的。情况二节点只有左、右指针没有parent指针root已知思路有两种情况一是要找的这两个节点a, b在要遍历的节点root的两侧那么这个节点就是这两个节点的最近公共父节点 二是两个节点在同一侧则 root-left 或者 root-right 为 NULL另一边返回a或者b。那么另一边返回的就是他们的最小公共父节点。 递归有两个出口一是没有找到a或者b则返回NULL二是只要碰到a或者b就立刻返回。
// 二叉树结点的描述 typedef struct BiTNode { char data; struct BiTNode lchild, rchild; // 左右孩子 }BinaryTreeNode; // 节点只有左指针、右指针没有parent指针root已知BinaryTreeNode findLowestCommonAncestor(BinaryTreeNode root , BinaryTreeNode* a , BinaryTreeNode* b){ if(root NULL) return NULL; if(root a || root b) return root;BinaryTreeNode* left findLowestCommonAncestor(root-lchild , a , b);BinaryTreeNode* right findLowestCommonAncestor(root-rchild , a , b); if(left right) return root; return left ? left : right;}情况三 二叉树是个二叉查找树且root和两个节点的值(a, b)已知// 二叉树是个二叉查找树且root和两个节点的值(a, b)已知BinaryTreeNode* findLowestCommonAncestor(BinaryTreeNode* root , BinaryTreeNode* a , BinaryTreeNode* b){ char min , max; if(a-data b-data)min a-data , max b-data; elsemin b-data , max a-data; while(root){ if(root-data min root-data max) return root; else if(root-data min root-data max)root root-rchild; elseroot root-lchild;} return NULL;}1、二叉树定义 typedef struct BTreeNodeElement_t_ { void *data;} BTreeNodeElement_t; typedef struct BTreeNode_t_ {BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTreeNode_t_ *m_pRight;} BTreeNode_t;2、查找二叉树中两个节点的最低祖先节点或最近公共父节点等 最低祖先节点就是从根节点遍历到给定节点时的最后一个相同节点
例如 A B C D E F G H I J K L M N O
如上图H和J的最低祖先节点是B。
因为从根节点A到H的链路为 A B D H
从根节点A到J的链路为 A B E J
查看链路节点可知B是最后一个相同节点也就是所谓的最近公共父节点或者说最低祖先节点。 1递归方式
如果给定pRoot是NULL即空树则返回的公共节点自然就是NULL
如果给定pRoot与两个节点中任何一个相同说明pRoot在就是所要找的两个节点之一则直接返回pRoot表明在当前链路中找到至少一个节点
如果给定pRoot不是两个节点中任何一个则说明需要在pRoot的左右子树中重新查找此时有三种情况两个节点都在左子树上两个节点都在右子树上一个在左子树一个在右子树上具体来说就是 情况一如果左子树查找出的公共节点是NULL则表明从左子树根节点开始到左子树的所有叶子节点等所有节点中没有找到两个节点中的任何一个这就说明这两个节点不在左子树上不在左子树则必定在右子树上 情况二如果右子树查找的公共节点是NULL说明在右子树中无法找到任何一个节点则两个节点必定在左子树上 情况三 如果左右子树查找的公共节点都不是NULL说明左右子树中各包含一个节点则当前节点pRoot就是最低公共节点返回就可以了。 三种情况是互斥的 只能是其中之一。 BTreeNode_t *GetLastCommonParent( BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot NULL ) //说明是空树不用查找了也就找不到对应节点则返回NULL return NULL; if( pRoot pNode1 || pRoot pNode2 )//说明在当前子树的根节点上找到两个节点之一 return pRoot; BTreeNode_t *pLeft GetLastCommonParent( pRoot-m_pLeft, pNode1, pNode2); //左子树中的查找两个节点并返回查找结果BTreeNode_t *pRight GetLastCommonParent( pRoot-m_pRight, pNode1, pNode2);//右子树中查找两个节点并返回查找结果 if( pLeft NULL )//如果在左子树中没有找到则断定两个节点都在右子树中可以返回右子树中查询结果否则需要结合左右子树查询结果共同断定 return pRight; if ( pRight NULL )//如果在右子树中没有找到则断定两个节点都在左子树中可以返回左子树中查询结果否则需要结合左右子树查询结果共同断定 return pLeft; return pRoot;//如果在左右子树中都找两个节点之一则pRoot就是最低公共祖先节点返回即可。}2非递归方式 BTreeNode_t *GetLastCommonParentBTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot NULL || pNode1 NULL || pNode2 NULL) return NULL; vector BTreeNode_t * vec1;//用来保存从根节点到指定节点的遍历路径前序遍历 vector BTreeNode_t * vec2; stack BTreeNode_t * st; bool findflag1 false; bool findflag2 false;BTreeNode_t *commonParent NULL; while( pRoot ! NULL || !st.empty() ){ while( pRoot ! NULL ){ if( findflag1 false){//没有找出所有的节点从根节点到指定节点在遍历时继续入栈vec1.push_back( pRoot); if( pRoot pNode1)//找到则设置标志位findflag1 true;} if( findflag2 false ){vec1.push_back( pRoot); if( pRoot pNode2 )findflag2 true;} if( findflag1 true findflag2 true)//如果都已找到则退出 break; st.push( pRoot);pRoot pRoot-m_pLeft;} while( !st.empty()){pRoot st.top();st.pop();pRoot pRoot-right; if( findflag1 false )//没有找到全部路径节点时就需要将错误路径节点退出vec1.pop_back(); if( findflag2 false )vec2.pop_back();} if( findflag1 true findflag2 true)//如果都已找到则退出 break; } if( findflag1 true findflag2 true){//在两个遍历路径上查找最后一个相同的节点就是最低公共祖先节点最近公共父节点 vector BTreeNode_t * ::iterator iter1 vec1.begin(); vector BTreeNode_t * ::iterator iter2 vec2.begin(); while( iter1 ! vec1.end() iter2 ! vec2.end() ){ if( *iter1 *iter2) commonParent *iter1; else break; iter1; iter2;} } vec1.clear(); vec2.clear(); st.clear(); return commonParent;}/prepre
