Leetcode 236. Lowest Common Ancestor of a Binary Tree

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

思路：分别搜索p, q结点，保存搜索路径（逆序），比较路径中第一个相同的结点即为二者的最低共同祖先节点。

• Version 1

# 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: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root.val == p.val or root.val == q.val:
            return root

        p_path = []
        q_path = []
        self.dfs(root, p, p_path)
        self.dfs(root, q, q_path)

        for temp in p_path:
            if temp in q_path:
                return temp


    def dfs(self, root, target, result):
        if root is None:
            return False

        if root.val == target.val:
            result.append(root)
            return True

        if self.dfs(root.left, target, result) or self.dfs(root.right, target, result):
            result.append(root)
            return True
        else:
            return False

Reference

1. https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/