您好,登錄后才能下訂單哦!
本篇內容介紹了“python怎么求二叉樹的LCA”的有關知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領大家學習一下如何處理這些情況吧!希望大家仔細閱讀,能夠學有所成!
題目:求二叉樹的LCA,也就是兩個節點的最低公共祖先。比如上圖的二叉樹,節點2和8的LCA是6,節點2和4的LCA是2。
思路:觀察給定的二叉樹可知,二叉樹中任何節點:左節點的值 < 根節點的值 < 右節點的值。根據這個性質,可以做出如下判斷:
如果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
遞歸方法:
# 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
“python怎么求二叉樹的LCA”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站,小編將為大家輸出更多高質量的實用文章!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。