algorithm - 二叉树中的链表

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) 解决方案通过了。

感谢任何帮助。

谢谢！

标签： algorithmlinked-listbinary-tree

Answer 1

如果n是树中的顶点数，那么您的算法的最坏情况时间复杂度是 Θ(2 ⁿ ) 而不是O ( n ² )。

这种最坏的情况发生在树的每个非叶子节点只有一个孩子，链表的长度大于树的深度，并且树和链表中的所有节点都具有相同的值时。当这种情况发生时，你最终会进行所有的递归调用——你的if-conditions 总是得到满足——所以每次你调用traverse一个节点时，你都会在它的子节点上调用traverse 两次。因此，您traverse在根节点上调用一次，在其子节点上调用两次，对其孙子调用四次，对其曾孙调用八次，依此类推，如果有n 个节点，则为 Θ(2 ^{n )。}