管理网站建设哪家公司好,建设通网站查询单位,凡科互动小程序官网,网站设计注册怎么做1 问题
求二叉树中俩个节点的最低共同父节点#xff0c;比如二叉树如下 42 61 3 5 7 比如节点1和3两个节点的最低共同父节点是2#xff0c;节点3和5两个节点的最低共同父节点是4,节点5和6两个节点的最低共同父节点是6, 也有可能其中1个节点或者2个节点不…1 问题
求二叉树中俩个节点的最低共同父节点比如二叉树如下 42 61 3 5 7 比如节点1和3两个节点的最低共同父节点是2节点3和5两个节点的最低共同父节点是4,节点5和6两个节点的最低共同父节点是6, 也有可能其中1个节点或者2个节点不在二叉树里面那么他们就没有最低共同父节点。 2 分析 42 61 3 5 7
比如我们求节点1和3两个节点的最低共同父节点我们保存每个根节点到该节点的最短路径节点值比如节点1的路径就是4-2-1 然后节点3的路径是4-2-3,然后我们再把这个保存的2个路径依次从尾巴进行进行比较然后就能获取两个节点的最低共同父节点值。 3 代码实现
#include iostream
#include vector
#include stdlib.husing namespace std;typedef struct Tree
{int value;struct Tree* left;struct Tree* right;Tree(int value) : value(value), left(NULL), right(NULL) {}
} Tree;class CommonParentNode
{
public:bool hasPath(Tree* head, Tree* node, std::vectorTree * vector){if (head NULL)return false;///先把我们的遍历节点保存到vector里面去vector.push_back(head);if (head node)return true;//如果这样写只能说明子递归return值了但是这个函数没有返回值。if (head-left ! NULL hasPath(head-left, node, vector))return true;if (head-right ! NULL hasPath(head-right, node, vector))return true;//这里一定要调用pop_back函数如果这个节点的左右子节点都为空或者左子树或者右子树里面不包含这个我们的节点//这个节点就要弹出来如果没有这个函数那么我们的vector里面保存的先序遍历到这个节点的所有节点值//而不是根节点到这个节点的最短距离。vector.pop_back();return false;}Tree* getCommmonParent(Tree* node, Tree* node1, Tree* node2){if (node NULL || node1 NULL || node2 NULL){std::cout node NULL || node1 NULL || node2 NULL std::endl;return NULL;}vectorTree * vector1;vectorTree * vector2;bool result1 hasPath(node, node1, vector1);if (!result1)return NULL;bool result2 hasPath(node, node2, vector2);if (!result2)return NULL;//我们vector依次保存的是从头结点到该节点的路径我们遍历的时候应该从vector的尾巴开始遍历,注释的遍历错了要注意// for (int i 0; i vector1.size(); i)// {// for (int j 0; j vector2.size(); j)// {// //if (vector1[i]-value vector2[j]-value)// if (vector1[i] vector2[j])// {// std::cout common parent node value is vector1[i]-value std::endl;// return vector1[i];// }// }// } for (int i vector1.size() - 1; i 0; --i){for (int j vector2.size() - 1; j 0; --j){//if (vector1[i]-value vector2[j]-value)if (vector1[i] vector2[j]){return vector1[i];}}} return NULL; }
};int main() {Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7, *node8;node1 (Tree *)malloc(sizeof(Tree));node2 (Tree *)malloc(sizeof(Tree));node3 (Tree *)malloc(sizeof(Tree));node4 (Tree *)malloc(sizeof(Tree));node5 (Tree *)malloc(sizeof(Tree));node6 (Tree *)malloc(sizeof(Tree));node7 (Tree *)malloc(sizeof(Tree)); node8 (Tree *)malloc(sizeof(Tree)); node1-value 4;node2-value 2;node3-value 6;node4-value 1;node5-value 3;node6-value 5;node7-value 7;node8-value 8;node1-left node2;node1-right node3;node2-left node4;node2-right node5;node3-left node6;node3-right node7;node4-left NULL;node4-right NULL;node5-left NULL;node5-right NULL;node6-left NULL;node6-right NULL;node7-left NULL;node7-right NULL;/*** 42 61 3 5 7 **/CommonParentNode commonParentNode;Tree *commonTreeNode NULL;commonTreeNode commonParentNode.getCommmonParent(node1, node5, node7);if (!commonTreeNode){std::cout the two node do not find commonTreeNode std::endl;return -1;}std::cout commonTreeNode parent node value is commonTreeNode-value std::endl;return 0;
} 4 运行结果
commonTreeNode parent node value is 4 5 总结
这个题目的思路是保存根节点到每个节点中途最短路径父节点值然后进行比较同时我们应该可以知道求根节点到该节点最短路径的每个节点值就是vector里面保存的每个节点同时也知道根节点到该节点的高度值也就是这个vecter里面保存数据的大小既vector.size()函数的值代码和上面部分代码一样。
bool hasPath(Tree* head, Tree* node, std::vectorTree * vector){if (head NULL)return false;///先把我们的遍历节点保存到vector里面去vector.push_back(head);if (head node)return true;//如果这样写只能说明子递归return值了但是这个函数没有返回值。if (head-left ! NULL hasPath(head-left, node, vector))return true;if (head-right ! NULL hasPath(head-right, node, vector))return true;//这里一定要调用pop_back函数如果这个节点的左右子节点都为空或者左子树或者右子树里面不包含这个我们的节点//这个节点就要弹出来如果没有这个函数那么我们的vector里面保存的先序遍历到这个节点的所有节点值//而不是根节点到这个节点的最短距离。vector.pop_back();return false;}
很经典的代码。
