Shulou(Shulou.com)06/02 Report--

This article is to share with you about how to find the smallest common parent node of the python binary tree. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it.

The problem is to find out the smallest common parent node (LCA Lowest Common Ancestor) of two points in the binary tree, such as the following figure, for example, the common parent node of 5 and 1 is 3, and the smallest common parent node of 6 and 7 is 5; and the smallest common parent node of 5 and 4 is 5 itself.

After considering it, in fact, the idea is very simple, first of all, we use the preorder or hierarchy to traverse the binary tree to get the node queue, because the preorder and hierarchy traverse the parent node first and then the child node, so the parent node of the node behind the queue must exist in the queue. Then traverse the node queue in reverse order from back to front. If the parent node of p and Q is given, it will be replaced by its parent node. If p and Q are the same node, it is the smallest common parent node.

The code is as follows: use hierarchical traversal to determine whether pfocus Q has been read; if all read stop traversal, avoid reading unnecessary data.

# Definition for a binary tree node.# class TreeNode:# def _ init__ (self, x): # self.val = x # self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor (self, root: 'TreeNode', p:' TreeNode' Q: 'TreeNode')->' TreeNode': preNodeList = [] checkList = [root] count = 2 while count > 0: nextList = [] for node in checkList: preNodeList.append (node) if node = = p or node = = Q: count = count-1 If count = = 0: pass if node.left! = None: nextList.append (node.left) if node.right! = None: nextList.append (node.right) checkList = nextList while packs = Q: currentNode = preNodeList.pop ( ) if currentNode.right = = p or currentNode.left = = p: P = currentNode if currentNode.right = = Q or currentNode.left = = Q: Q = currentNode return p above is how to find the smallest common parent node of two points of python binary tree The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.