后序非递归 求节点路径

先求得两个节点的路径，在求公共节点

样例

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findpath(self, root, target):
        stack = []
        p, last_visited = root, None
        while stack or p:
            if p:
                stack.append(p)
                p = p.left
            else:
                p = stack[-1]
                if p.right and p.right != last_visited:
                    p = p.right
                else:
                    tmp = stack.pop(-1)
                    if tmp == target:
                        return stack+[tmp]
                    last_visited = p
                    p = None
        return []

    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)
        if not (path1 and path2):
            return None
        k1, k2 = len(path1), len(path2)
        path, k = (path1, k1-k2) if k1 > k2 else (path2, k2-k1)
        for _ in range(k):
            path.pop(-1)
        for i in range(len(path1)-1, -1, -1):
            if path1[i] == path2[i]:
                return path1[i]
        return None