C++ implements the method of finding the lowest common parent node

This paper illustrates the method of finding the lowest common parent node in C++. Share with you for your reference. Specific methods are as follows:

The lowest common parent node, which makes sense.

Idea 1: the lowest common parent node satisfies the condition that two nodes are located in their left and right subtrees respectively. Then define two bool variables, leftFlag and rightFlag. If leftFlag is true in the left subtree and rightFlag is true in the right subtree, the condition can only be satisfied when leftFlag == rightFlag == true.

The implementation code is as follows:

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft),
 right(pRight) {}
 Node *left;
 Node *right;
 int data;
};

Node *constructNode(Node **pNode1, Node **pNode2)
{
 Node *node12 = new Node(12);
 Node *node11 = new Node(11);
 Node *node10 = new Node(10);
 Node *node9 = new Node(9, NULL, node12);
 Node *node8 = new Node(8, node11, NULL);
 Node *node7 = new Node(7);
 Node *node6 = new Node(6);
 Node *node5 = new Node(5, node8, node9);
 Node *node4 = new Node(4, node10);
 Node *node3 = new Node(3, node6, node7);
 Node *node2 = new Node(2, node4, node5);
 Node *node1 = new Node(1, node2, node3);

 *pNode1 = node6;
 *pNode2 = node12;

 return node1;
}

bool isNodeIn(Node *root, Node *node1, Node *node2)
{
 if (node1 == NULL || node2 == NULL)
 {
 throw("invalid node1 and node2");
 return false;
 }
 if (root == NULL)
 return false;

 if (root == node1 || root == node2)
 {
 return true;
 }
 else
 {
 return isNodeIn(root->left, node1, node2) || isNodeIn(root->right, node1, node2);
 }
}

Node *lowestFarther(Node *root, Node *node1, Node *node2)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 {
 return NULL;
 }
 
 bool leftFlag = false;
 bool rightFlag = false;
 leftFlag = isNodeIn(root->left, node1, node2);
 rightFlag = isNodeIn(root->right, node1, node2);

 if (leftFlag == true && rightFlag == true)
 {
 return root;
 }
 else if (leftFlag == true)
 {
 return lowestFarther(root->left, node1, node2);
 }
 else
 {
 return lowestFarther(root->right, node1, node2);
 }
}

void main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 cout << "node1: " << node1->data << endl;
 cout << "node2: " << node2->data << endl;
 cout << "root: " << root->data << endl;

 Node *father = lowestFarther(root, node1, node2);

 if (father == NULL)
 {
 cout << "no common father" << endl;
 }
 else
 {
 cout << "father: " << father->data << endl;
 }
}

This type of question often comes up in interviews, so consider the following:

1. Node1 and node2 point to the same node, how to deal with this
2. Is it possible for node1 or node2 not to be leaf nodes
3. Must node1 or node2 be in the tree

There is also an efficiency problem to consider, the above code USES two recursive functions, and there is unnecessary recursive process, think carefully, actually a recursive process is enough to solve this problem

The implementation code is as follows:

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i),
 left(pLeft), right(pRight) {}
 int data;
 Node *left;
 Node *right;
};

Node *constructNode(Node **pNode1, Node **pNode2) 
{ 
 Node *node12 = new Node(12); 
 Node *node11 = new Node(11); 
 Node *node10 = new Node(10); 
 Node *node9 = new Node(9, NULL, node12); 
 Node *node8 = new Node(8, node11, NULL); 
 Node *node7 = new Node(7); 
 Node *node6 = new Node(6); 
 Node *node5 = new Node(5, node8, node9); 
 Node *node4 = new Node(4, node10); 
 Node *node3 = new Node(3, node6, node7); 
 Node *node2 = new Node(2, node4, node5); 
 Node *node1 = new Node(1, node2, node3); 

 *pNode1 = node6; 
 *pNode2 = node5; 

 return node1; 
}

bool lowestFather(Node *root, Node *node1, Node *node2, Node *&dest)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 return false;
 if (root == node1 || root == node2)
 return true;

 bool leftFlag = lowestFather(root->left, node1, node2, dest);
 bool rightFlag = lowestFather(root->right, node1, node2, dest);
 
 if (leftFlag == true && rightFlag == true)
 {
 dest = root;
 }
 if (leftFlag == true || rightFlag == true)
 return true;
}

int main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 bool flag1 = false;
 bool flag2 = false;
 Node *dest = NULL;
 bool flag = lowestFather(root, node1, node2, dest);

 if (dest != NULL)
 {
 cout << "lowest common father: " << dest->data << endl;
 }
 else
 {
 cout << "no common father!" << endl;
 }

 return 0;
}

Here's another way to write it:

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i),
 left(pLeft), right(pRight) {}
 int data;
 Node *left;
 Node *right;
};

Node *constructNode(Node **pNode1, Node **pNode2) 
{ 
 Node *node12 = new Node(12); 
 Node *node11 = new Node(11); 
 Node *node10 = new Node(10); 
 Node *node9 = new Node(9, NULL, node12); 
 Node *node8 = new Node(8, node11, NULL); 
 Node *node7 = new Node(7); 
 Node *node6 = new Node(6); 
 Node *node5 = new Node(5, node8, node9); 
 Node *node4 = new Node(4, node10); 
 Node *node3 = new Node(3, node6, node7); 
 Node *node2 = new Node(2, node4, node5); 
 Node *node1 = new Node(1, node2, node3); 

 *pNode1 = node11; 
 *pNode2 = node12; 

 return node1; 
}

Node* lowestFather(Node *root, Node *node1, Node *node2)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 return NULL;
 if (root == node1 || root == node2)
 return root;

 Node* leftFlag = lowestFather(root->left, node1, node2);
 Node* rightFlag = lowestFather(root->right, node1, node2);

 if (leftFlag == NULL)
 return rightFlag;
 else if (rightFlag == NULL)
 return leftFlag;
 else
 return root;
}

int main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 bool flag1 = false;
 bool flag2 = false;
 Node *dest = NULL;
 Node* flag = lowestFather(root, node1, node2);

 if (flag != NULL)
 {
 cout << "lowest common father: " << flag->data << endl;
 }
 else
 {
 cout << "no common father!" << endl;
 }

 return 0;
}

Hope that this article is helpful to the learning of C++ programming algorithm design.