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不在同一颗子树上的分割点,这个分割点就是公共祖先