Dig into the binomial tree of the lowest common parent of two nodes
- 2020-04-01 23:46:42
- OfStack
Title: the nodes of binary tree are defined as follows:
Input two nodes in the binary tree and output their lowest common parent.
Analysis: finding the lowest common node of two nodes is a common problem in interview. There are at least two variants of this problem.
The first variant is the binary tree, which is a special binary tree: find the binary tree. That is, the tree is sorted, the nodes in the left child tree are smaller than the parent, and the nodes in the right child tree are larger than the parent. We just have to start at the root and compare it to two nodes. If the value of the current node is larger than that of both nodes, then the lowest common parent must be in the left child tree of the current node. If the value of the current node is smaller than that of both nodes, the lowest common parent must be in the right child tree of the current node.
The second variant is that the tree is not necessarily a binary tree, each node has a pointer to its parent. So we can start at any node and get a one-way list to the root. So the problem turns into finding the first common node of two one-way lists.
Now let's go back to the problem itself. A common parent is when both nodes appear in the child tree of that node. So we can define a function that determines whether a node's subtree contains another node. This is not very difficult, we can use recursive method to achieve:
We can start at the root and determine whether the left and right subtrees of the tree rooted at the current node contain the two nodes we are looking for. If both nodes appear in its left child tree, the lowest common parent also appears in its left child tree. If both nodes appear in its right child tree, the lowest common parent also appears in its right child tree. If there are two nodes, one in the left subtree and one in the right subtree, then the current node is the lowest common parent. Based on this idea, we can write the following code:
Then let's analyze the efficiency of this method. The essence of the HasNode function is to traverse a tree with a time complexity of O(n) (n is the number of nodes in the tree). Since we start at root, we call the function HasNode for each node. So the total time complexity is order n^2.
After careful analysis of the above code, it is not difficult to find that we need to traverse every node of the tree to determine whether a tree rooted at a node contains a node. Next, we can determine whether the tree with the left child or the right root has any nodes in it. The second pass is actually done before the first pass. Because of the repeated traversal, this method is definitely not the best in terms of time efficiency.
We mentioned earlier that if a node has a pointer to its parent, we can turn the problem into finding the joint of two lists. Now we can figure out how to get this list. We can make a few changes here:
Because this path starts at a node. The lowest common parent is the last common node in the path:
Now that you have the first two children, it's easy to find the lowest common parent of two nodes. Let's figure out the two paths from the root to the two nodes, and then figure out the last common node of the two paths. The code is as follows:
The time complexity of this idea is O(n), and the time efficiency is much better than the first method. But it's also important to note that this approach, which requires two linked lists to hold the path, is not as efficient spatially as the first approach.
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
Input two nodes in the binary tree and output their lowest common parent.
Analysis: finding the lowest common node of two nodes is a common problem in interview. There are at least two variants of this problem.
The first variant is the binary tree, which is a special binary tree: find the binary tree. That is, the tree is sorted, the nodes in the left child tree are smaller than the parent, and the nodes in the right child tree are larger than the parent. We just have to start at the root and compare it to two nodes. If the value of the current node is larger than that of both nodes, then the lowest common parent must be in the left child tree of the current node. If the value of the current node is smaller than that of both nodes, the lowest common parent must be in the right child tree of the current node.
The second variant is that the tree is not necessarily a binary tree, each node has a pointer to its parent. So we can start at any node and get a one-way list to the root. So the problem turns into finding the first common node of two one-way lists.
Now let's go back to the problem itself. A common parent is when both nodes appear in the child tree of that node. So we can define a function that determines whether a node's subtree contains another node. This is not very difficult, we can use recursive method to achieve:
/*
// If the tree with head pHead has a node pNode, return true.
// Otherwise return false.
*/
bool HasNode(TreeNode* pHead, TreeNode* pNode)
{
if(pHead == pNode)
return true;
bool has = false;
if(pHead->m_pLeft != NULL)
has = HasNode(pHead->m_pLeft, pNode);
if(!has && pHead->m_pRight != NULL)
has = HasNode(pHead->m_pRight, pNode);
return has;
}
We can start at the root and determine whether the left and right subtrees of the tree rooted at the current node contain the two nodes we are looking for. If both nodes appear in its left child tree, the lowest common parent also appears in its left child tree. If both nodes appear in its right child tree, the lowest common parent also appears in its right child tree. If there are two nodes, one in the left subtree and one in the right subtree, then the current node is the lowest common parent. Based on this idea, we can write the following code:
/*
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
*/
TreeNode* LastCommonParent_1(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
// check whether left child has pNode1 and pNode2
bool leftHasNode1 = false;
bool leftHasNode2 = false;
if(pHead->m_pLeft != NULL)
{
leftHasNode1 = HasNode(pHead->m_pLeft, pNode1);
leftHasNode2 = HasNode(pHead->m_pLeft, pNode2);
}
if(leftHasNode1 && leftHasNode2)
{
if(pHead->m_pLeft == pNode1 || pHead->m_pLeft == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pLeft, pNode1, pNode2);
}
// check whether right child has pNode1 and pNode2
bool rightHasNode1 = false;
bool rightHasNode2 = false;
if(pHead->m_pRight != NULL)
{
if(!leftHasNode1)
rightHasNode1 = HasNode(pHead->m_pRight, pNode1);
if(!leftHasNode2)
rightHasNode2 = HasNode(pHead->m_pRight, pNode2);
}
if(rightHasNode1 && rightHasNode2)
{
if(pHead->m_pRight == pNode1 || pHead->m_pRight == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pRight, pNode1, pNode2);
}
if((leftHasNode1 && rightHasNode2) || (leftHasNode2 && rightHasNode1))
return pHead;
return NULL;
}
Then let's analyze the efficiency of this method. The essence of the HasNode function is to traverse a tree with a time complexity of O(n) (n is the number of nodes in the tree). Since we start at root, we call the function HasNode for each node. So the total time complexity is order n^2.
After careful analysis of the above code, it is not difficult to find that we need to traverse every node of the tree to determine whether a tree rooted at a node contains a node. Next, we can determine whether the tree with the left child or the right root has any nodes in it. The second pass is actually done before the first pass. Because of the repeated traversal, this method is definitely not the best in terms of time efficiency.
We mentioned earlier that if a node has a pointer to its parent, we can turn the problem into finding the joint of two lists. Now we can figure out how to get this list. We can make a few changes here:
/*
// Get the path form pHead and pNode in a tree with head pHead
*/
bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)
{
if(pHead == pNode)
return true;
path.push_back(pHead);
bool found = false;
if(pHead->m_pLeft != NULL)
found = GetNodePath(pHead->m_pLeft, pNode, path);
if(!found && pHead->m_pRight)
found = GetNodePath(pHead->m_pRight, pNode, path);
if(!found)
path.pop_back();
return found;
}
Because this path starts at a node. The lowest common parent is the last common node in the path:
/*
// Get the last common Node in two lists: path1 and path2
*/
TreeNode* LastCommonNode
(
const std::list<TreeNode*>& path1,
const std::list<TreeNode*>& path2
)
{
std::list<TreeNode*>::const_iterator iterator1 = path1.begin();
std::list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while(iterator1 != path1.end() && iterator2 != path2.end())
{
if(*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
iterator2++;
}
return pLast;
}
Now that you have the first two children, it's easy to find the lowest common parent of two nodes. Let's figure out the two paths from the root to the two nodes, and then figure out the last common node of the two paths. The code is as follows:
/*
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
*/
TreeNode* LastCommonParent_2(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
std::list<TreeNode*> path1;
GetNodePath(pHead, pNode1, path1);
std::list<TreeNode*> path2;
GetNodePath(pHead, pNode2, path2);
return LastCommonNode(path1, path2);
}
The time complexity of this idea is O(n), and the time efficiency is much better than the first method. But it's also important to note that this approach, which requires two linked lists to hold the path, is not as efficient spatially as the first approach.