Detailed explanation of the lowest common parent node of two nodes in the binary tree

Topic: The node definition of a binary tree is as follows:

Enter two nodes in the binary tree and output the lowest common parent node in the number.
Analysis: Finding the lowest common node of two nodes in the number is a common problem in the interview. There are at least two variants of this problem.
The first variant is that the binary tree is a special binary tree: looking for a binary tree.That is, the trees are sorted, and the nodes located on the left subtree are smaller than the parent node, while the nodes located on the right subtree are larger than the parent node. We just need to compare with the two nodes starting from the root node. If the value of the current node is larger than both nodes, 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 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, and each node has a pointer to its parent node.So we can start from any node and get a one-way linked list that reaches the root node of the tree. Therefore, this problem is converted to finding the first common node of two unidirectional linked lists.
Now let's go back to the question itself. The so-called common parent node means that both nodes appear in the subtree of this node. Therefore, we can define a function to determine whether a node's subtree contains another node. This is not a difficult thing, we can use recursive methods to achieve:

We can start from the root node and judge whether the left and right subtrees in the tree rooted with the current node include the two nodes we are looking for. If both nodes appear in its left subtree, the lowest common parent node also appears in its left subtree. If both nodes appear in its right subtree, the lowest common parent node also appears in its right subtree. If one of the two nodes appears in the left subtree and the other appears in the right subtree, then the current node is the lowest common parent node. Based on this idea, we can write the following code:

Next, let’s analyze the efficiency of this method. The essence of the function HasNode is to traverse a tree, and its time complexity is O(n) (n is the number of nodes in the tree). Since we start with the root node, we need to call the function HasNode for each node. Therefore, the total time complexity is O(n^2).
We carefully analyze the above code and it is not difficult to find that when we judge whether a tree with a node as the root contains a certain node, we need to traverse each node of the tree. Next, we will determine whether the tree with the left sub-node or the right node is the root contains the nodes to be found, and it still needs to be traversed. The second traversal operation was actually done in the first traversal. Due to the repeated traversal, this method is definitely not the best time efficiency.
We mentioned earlier that if there is a pointer to the parent node in the node, we can convert the problem into finding the common node of the two linked lists. Now we can find a way to get this linked list. Let's make a little change here:

Because this path starts from the node. The lowest common parent node is the last common node in the path:

With the first two child functions, it is easy to find the lowest common parent node of the two nodes. We first find the two paths from the root node to the two nodes, and then find 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 at the same time, we should also note that this idea requires two linked lists to save the path, and the space efficiency is not as good as the first method.