题目描述

剑指offer第一期week3周四的第二道题

思路原创，如有一样，纯属巧合

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

思路

• 给每个元素编码，我假设了根的编码为’#’,向左为‘0’，向右为‘1’
• 比较每个元素编码，如果两者编码相等，则移动返回值指向，不相等则返回

如题目给的样例5,1。则编码为"#0","#1"，比较编码，发现第二个编码不相等，返回第一个元素，即root
如题目给的样例5,4。则编码为"#0","#000"，比较编码，发现第三个编码不相等，返回第二个元素，即root.left

class Solution:
    def __init__(self):
        self.code = dict()

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.code[root.val] = '#'
        def preorder(root):  # 编码
            if root.left:
                self.code[root.left.val] = self.code[root.val] + '0'
                preorder(root.left)
            if root.right:
                self.code[root.right.val] = self.code[root.val] + '1'
                preorder(root.right)

        def LCA(p, q):  # 比较编码
            res = root
            for c1, c2 in zip(self.code[p][1:], self.code[q][1:]):
                if c1 == c2:
                    if c1 == '0':
                        res = res.left
                    else:
                        res = res.right
                else:
                    break
            return res
        preorder(root)
        return LCA(p.val, q.val)

成绩

执行用时 : 204 ms, 在Lowest Common Ancestor of a Binary Tree的Python3提交中击败了9.03% 的用户
内存消耗 : 126.2 MB, 在Lowest Common Ancestor of a Binary Tree的Python3提交中击败了5.11% 的用户

说明

容易理解，效率不高，重在参与