Leetcode 236. Самый низкий общий предок бинарного дерева? - PullRequest
Новая
       43

Leetcode 236. Самый низкий общий предок бинарного дерева?

0 голосов
/ 25 октября 2018

У меня возникли некоторые проблемы по этому вопросу.Ниже приведен исходный вопрос:

enter image description here

Я решил использовать стек для хранения трассы, а затем выполнить DFS от левого поддерева к правому поддереву.Во время процесса, когда он находит q или p, просто поместите трассировку в новый стек (stack1).Во второй раз, когда мы находим остаток от q или p, мы можем проверить, что длина стека1 равна двум, поэтому мы вырываемся из итерации и сравниваем две трассы, чтобы найти ответ.

После завершения яЯ запустил несколько пользовательских тестов, все они работали правильно.Но после отправки система сказала «Ошибка выполнения».Может ли кто-нибудь помочь мне понять, почему я не прав?Любые комментарии или предложения будут так оценены.Спасибо.

Это мой оригинальный ответ: 

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

from copy import deepcopy
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        stack1, stack, last, sign = [], [], root, False
        stack.append(root)
        if root == q or root == p:
            stack1.append([root])

        while stack:
            while root.left and root.left != last and root.right != last:
                last = root
                root = root.left
                stack.append(root)
                if root == p or root == q:
                    stack1.append(deepcopy(stack))
                    if len(stack1) == 2:
                        sign = True
                        break
            if sign:
                break

            if root.right != last and root.right:
                ast = root
                root = root.right
                stack.append(root)
                if root == p or root == q:
                    stack1.append(deepcopy(stack))
                    if len(stack1) == 2:
                        break
            else:
                last = stack.pop()
                root = stack[-1]

        for x in stack1[0][::-1]:
            for y in stack1[1][::-1]:
                if y.val == x.val:
                    return x
...