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

This article introduces the relevant knowledge of "how to find the LCA of a binary tree by python". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Topic: find the LCA of the binary tree, that is, the lowest common ancestor of the two nodes. For example, in the binary tree above, the LCA of nodes 2 and 8 is 6, and the LCA of nodes 2 and 4 is 2.

Idea: looking at a given binary tree, any node in the binary tree: the value of the left node

< 根节点的值 < 右节点的值。根据这个性质，可以做出如下判断： 如果p、q都比根节点小，则在左子树中递归查找最低公共祖先节点。 如果p、q都比根节点大，则在右子树中递归查找最低公共祖先节点。 如果p、q一个比根节点大，一个比根节点小，或者有一个等于根节点，则根节点即为最低公共祖先节点。 Language : cpp 递归方法： /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (p->

Val

< root->

Val & & root- > val > Q-> val) return lowestCommonAncestor (root- > left, p, Q); else if (p-> val > root- > val & & root- > val

< q->

Val) return lowestCommonAncestor (root- > right, p, Q); elsereturn root;}}

Language: python

Recursive method:

# Definition for a binary tree node.# class TreeNode (object): # def _ init__ (self, x): # self.val = x # self.left = None# self.right = Noneclass Solution (object): def lowestCommonAncestor (self, root, p, Q): "": type root: TreeNode: type p: TreeNode: type Q: TreeNode: rtype: TreeNode "" if p.val

< root.val >

Q.val:return self.lowestCommonAncestor (root.left, p, Q) elif p.val > root.val

< q.val:return self.lowestCommonAncestor(root.right, p, q)else:return root 迭代方法： # Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""" :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """while True:if p.val < root.val >

Q.val: root = root.leftelif p.val > root.val < q.val: root = root.rightelse:return root "how to find the LCA of a binary tree by python" ends here. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.