二叉树最近公共父节点: 有一个普通二叉树，AB分别为两个子节点，求AB最近的公共父节点。 #Algorithm #Python

find_common_root.py

# find_common_root.py


class TreeNode():
    def __init__(self, left, right, val):
        self.val = val
        self.left = left
        self.right = right

    def getPath(self, root, decNode, array):
        findResult = False

        if root is not None:
            if root == decNode:
                array.append(root)
                findResult = True
            if not findResult and root.left is not None:
                findResult = self.getPath(root.left, decNode, array)
                if findResult:
                    array.append(root)
            if not findResult and root.right is not None:
                findResult = self.getPath(root.right, decNode, array)
                if findResult:
                    array.append(root)
        return array


def getCommonRoot(root, a, b):
    common = None
    pathA = []
    pathB = []
    a.getPath(root, a, pathA)
    b.getPath(root, b, pathB)
    for nodeA in pathA:
        for nodeB in pathB:
            if nodeA == nodeB:
                common = nodeA
                break
        if common is not None:
            break
    return common


if __name__ == '__main__':
    g = TreeNode(None, None, 7)
    f = TreeNode(None, None, 6)
    e = TreeNode(None, None, 5)
    d = TreeNode(None, None, 4)
    c = TreeNode(f, g, 3)
    b = TreeNode(d, e, 2)
    a = TreeNode(b, c, 1)

    test = None
    test = getCommonRoot(a, b, d)
    if test is not None:
        print test.val