How do the nearest common ancestors of python binary trees understand
This article will explain in detail how to understand the recent public ancestors of the python binary tree. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have some understanding of the relevant knowledge after reading this article.
Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.
The recent common ancestor in Baidu encyclopedia is defined as: "for the two nodes p and Q with root tree T, the nearest common ancestor is expressed as a node x, satisfying that x is the ancestor of p and Q and that x is as deep as possible (a node can also be its own ancestor)."
For example, a binary tree is given as follows: root = [3pd5, 1, 6, 2, 0, 0, 8, null, and 7]
Example 1:
Input: root = [3, 5, 1, 1, 6, 6, 2, 0, 8], p = 5, Q = 1 output: 3 explanation: the nearest common ancestor of node 5 and node 1 is node 3.
Example 2:
Input: root = [3, 5, 1, 6, 2, 0, 8, 7, 4], p = 5, Q = 4
Answer:
1public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode Q) {
2 if (root = = null | | root = = p | | root = = Q)
3 return root
4 TreeNode left = lowestCommonAncestor (root.left, p, Q)
5 TreeNode right = lowestCommonAncestor (root.right, p, Q)
6 return left = = null? Right: right = = null? Left: root
7}
Parsing:
Through the recursive way, look down from his left and right child nodes, if they are not empty, it means that their nearest common ancestor node must be the current root node, if one is empty, their nearest common ancestor node is on the other child node. This solution is very similar to DFS, starting with the leftmost leaf node, and then going back online. Let's take a look at a solution.
1public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode Q) {
2 Map parent = new HashMap ()
3 Deque stack = new ArrayDeque ()
4 parent.put (root, null)
5 stack.push (root)
6 while (! parent.containsKey (p) | |! parent.containsKey (Q)) {
7 TreeNode node = stack.pop ()
8 if (node.right! = null) {
9 parent.put (node.right, node)
10 stack.push (node.right)
11}
12 if (node.left! = null) {
13 parent.put (node.left, node)
14 stack.push (node.left)
15}
16}
17 Set ancestors = new HashSet ()
18 while (p! = null) {
19 ancestors.add (p)
20 p = parent.get (p)
21}
22 while (! ancestors.contains (Q))
23 Q = parent.get (Q)
24 return q
25}
In Map, key records the current node, value records the parent node of the current node, and the first while loop uses DFS. Until the p and Q nodes are found, the second while loop takes the p node and its parent node, as well as the parent node of the parent node. Are added to the ancestors collection, and the third while loop constantly fetches the Q node and its parent node and the parent node of the parent node. Until it can be found in ancestors, the ancestor node of p is also the ancestor node of Q, and it is also the closest.
On the recent public ancestors of python binary tree how to understand how to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.
