首页 > 代码库 > 二叉树(13)----求二叉树中任意两个节点之间的距离,递归和非递归
二叉树(13)----求二叉树中任意两个节点之间的距离,递归和非递归
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、二叉树中任意两个节点之间的距离
根本上是求二叉树中任意两个节点的最近祖先节点(最近公共父节点),求出最近祖先节点之后,由最近祖先节点到这两个节点的距离之和就是。
(1)递归方式
首先根据递归方式求出最近祖先节点;
然后根据递归方式,从最近祖先节点通过前序遍历方式遍历到给定节点,找到路径,同时计算出距离即可(本处距离可以认为是两节点之间的边可以看成是单位1)
(2)非递归方式
int GetLenBetweenNodes( BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot == NULL || pNode1 == NULL || pNode2 == NULL ) return 0; if( pNod1 == pNod2 ) return 0; vector <BTreeNode_t *> vec1; vector <BTreeNode_t *> vec2; stack <BTreeNode_t *> st; bool findNod1 = false; bool findNod2 = false; int len = 0; while( !st.empty() || pRoot != NULL ){//前序遍历,找到从根节点到给定节点的路径 while( pRoot != NULL ){ if( findNod1 == false){ vec1.push_back( pRoot); if( pRoot == pNode1) findNod1 = true; } if( findNod2 == false){//没有找到完整路径,就增加节点 vec2.push_back( pRoot); if( pRoot == pNode2 ) findNod2 = true; } if( findNod1 && findNod2 )//都已找到,退出查找 break; st.push(pRoot); pRoot = pRoot->m_pLeft; } if( !st.empty() ){ pRoot = st.top(); st.pop(); pRoot = pRoot->m_pRight; if( findNod1 == false)//路径错误,则删除节点 vec1.pop_back(); if( findNod2 == false) vec2.pop_back(); } if( findNod1 && findNod2 )//都已找到,退出查找 break; } if( findNod1 && findNod2){ vector <BTreeNode_t *> :: iterator iter1 = vec1.begin(); vector< BTreeNode_t *> :: iterator iter2 = vec2.begin(); BTreeNode_t *lastCommonParent = NULL; int commonSize = 0; while( iter1 != vec1.end() && iter2 != vec2.end() ){//同时从根节点开始,遍历两个路径,找到最低祖先节点,并记录从根节点到最低祖先节点的长度 if( *iter1 == *iter2 ){ lastCommonParent = *iter1; ++commonSize; } else break; } len = vec1.size() + vec2.size() - 2*commonSIze;//两个路径长度-两个共同长度,就是最终距离 } vec1.clear(); vec2.clear(); st.clear(); return len; }
二叉树(13)----求二叉树中任意两个节点之间的距离,递归和非递归
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。