leetcode--Lowest Common Ancestor of a Binary Tree--ポイント

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
ここはBTです。BSTではありません。考えはrootからpとqのパスを見つけて最後の交点を見つけます。どのようにfind Pathに注意しますか？
再帰をどう使うかhttp://bookshadow.com/weblog/2015/07/13/leetcode-lowest-common-ancestor-binary-tree/
考え方1 findPath。post-orderを使う

class Solution(object):

    def findPath(self, root, target):

        stack = []
        pre = None
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:#     post order。        ，    ，   root，scan root     path
                peek = stack[-1]# the first value of peek should be the most left node
                if peek.right and pre != peek.right:
                    root = peek.right#     ，  pop   ，           pop
                else:#        ，           。
                    if peek == target:
                        return stack
                    pre = stack.pop()
                    root = None  #        


    def lowestCommonAncestor(self, root, p, q):
        """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """
        path1 = self.findPath(root, p)
        path2 = self.findPath(root, q)
        i = 0
        len1, len2 = len(path1), len(path2)
        while i < min(len1, len2) and path1[i] == path2[i] :
            i += 1
        i -= 1
        return path1[i]

ここではpreorderでstackのコードを直接持ってはいけません。pushのelementでstackに入れた後、探しているnodeかどうかを判断します。反例[2,null，1]は、1にとって最後のパスの結果は1だけです。したがって、次のようなパスのコードは正しくありません。上のコードを覚えてください。

        while stack or root:
            if root:
                stack.append(root)
                if root == target:
                    return stack
                root = root.left
            else:
                root = stack.pop()
                root = root.right

考え方2再帰

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """
        #   if root == None return root    if root == None :return None
        if root == None or root == p or root == q:
            return root

        # divide
        left = self.lowestCommonAncestor(root.left, p, q)#  p,q     LCA
        right = self.lowestCommonAncestor(root.right, p, q)#  p,q     LCA

        # conquer # right   None     p q root.right    LCA,     node         node      。
        if left and right:#     None，      LCA,      LCA,      LCA     root
            return root
        elif left:
            return left
        elif right:
            return right
        else:
            return None

findPath-postorderを自分で書き直します。

    def findPath(self, root, target):

        stack = []
        last = None
        while stack or root:
            if root:
                stack.append(root.val)
                #last = root      
                root = root.left
            else:#      None,           。      stack[-1]    ，       
                peek = stack[-1]
                if peek.right and last != peek.right:#    ，      scan。     if last == peek.right
                    root = root.right
                else:#    ，  ，      ，  last
                    if peek == target:
                        return stack
                    last = stack.pop()#        last  。
                    root = None#   。     last   ，   stack pop， stack     node，         stack[-1],          else