Связанный список в двоичном дереве

Question

Я пытаюсь решить: https://leetcode.com/contest/weekly-contest-178/problems/linked-list-in-binary-tree/

У меня есть следующее решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean ans;
    ListNode originalHead;
    public boolean isSubPath(ListNode head, TreeNode root) {
        this.ans = false;
        originalHead = head;
        traverse(head, root);
        return ans;
    }

    public void traverse(ListNode head, TreeNode root) {
        if(head == null) {
            ans = true;
            return;
        }
        if(root == null) return;

        if(!ans && root.val == head.val) traverse(head.next, root.right);
        if(!ans && root.val == head.val) traverse(head.next, root.left);
        if(!ans) traverse(originalHead, root.right);
        if(!ans) traverse(originalHead, root.left);
    }
}

Мне интересно, есть ли у этого решения время сложность O (n ^ 2) или нет. Я спрашиваю об этом, поскольку я сталкиваюсь с ошибкой Time Limit Exceeded для одного из тестов в наборе тестов.

Я вижу, что другие решения O (n ^ 2) проходят, хотя.

Цени любую помощь.

Спасибо!

Answer 1

Если n - это число вершин в дереве, то временная сложность вашего алгоритма в наихудшем случае составляет Θ (2 ⁿ ), а не O ( n ² ).

Этот наихудший случай возникает, когда у каждого неконечного узла дерева есть только один дочерний элемент, связанный список длиннее, чем дерево, и все узлы в дереве и связанного списка имеют одинаковое значение. Когда это происходит, вы в конечном итоге делаете все ваших рекурсивных вызовов - ваши if -условия всегда выполняются - поэтому каждый раз, когда вы вызываете traverse на узле, вы вызываете traverse дважды на его дочернем узле. Таким образом, вы вызываете traverse один раз для узла root, дважды для его дочернего элемента, четыре раза для своего внука, восемь раз для своего правнука и т. Д. c., Что составляет Θ (2 ⁿ ), если есть n узлов.