Leetcode235 二叉搜索树的最近公共祖先
题目描述
我的解法[递归]
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root, p, q): parrent_val = root.val p_val = p.val q_val = q.val if(p_val >parrent_val and q_val > parrent_val): return self.lowestCommonAncestor(root.right,p,q) #class: def function():return self.function elif(p_val < parrent_val and q_val < parrent_val): return self.lowestCommonAncestor(root.left,p,q) else: return root
迭代解法
class Solution: def lowestCommonAncestor(self, root, p, q): p_val = p.val q_val = q.val node = root while node: parent_val = node.val if p_val > parent_val and q_val > parent_val: node = node.right elif p_val < parent_val and q_val < parent_val: node = node.left else: return node
Note
class Solution: def function(self,a,b,c): # return function(a+1,b+1,c+1) 这种写法是错的 return self.function(a+1,b+1,c+1)
- 一开始看题目的时候没有注意是二叉搜索树的特性 浪费了时间
- 迭代的思路是寻找到让p和q不在同一颗子树上的分割点,这个分割点就是公共祖先
每日一题今天刷到了~