首页 > 代码库 > 二叉树两个结点的最低共同父节点
二叉树两个结点的最低共同父节点
后序遍历就行。
//寻找二叉树两个结点的最低共同父节点TreeNode *FindFirstCommonParentNode(TreeNode *pRoot, TreeNode *pNodeOne, TreeNode *pNodeTwo){ if (NULL == pRoot) { return NULL; } if (pRoot == pNodeOne || pRoot == pNodeTwo) { return pRoot; } TreeNode *pLeft = FindFirstCommonParentNode(pRoot->m_pLeft, pNodeOne, pNodeTwo); TreeNode *pRight = FindFirstCommonParentNode(pRoot->m_pRight, pNodeOne, pNodeTwo); if (NULL == pLeft) //1、左子树没有找到任何一个结点,则第一个公共父节点必定在右子树,而且找到第一个结点就是最低共同父节点 { return pRight; } else if (NULL == pRight) //2、右子树没有找到任何一个结点,则第一个公共父节点必定在左子树,而且找到第一个结点就是最低共同父节点 { return pLeft; } else //3、分别在结点的左右子树找到,则此节点必为第一个公共父节点 { return pRoot; }}
二叉树两个结点的最低共同父节点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。