二叉树中的链表

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)。我问这个是因为我在测试套件中的一个测试用例中遇到了超出时间限制的错误。

我确实看到其他 O(n^2) 解决方案通过了。

感谢任何帮助。

谢谢！

Answer 1

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

这种最坏的情况发生在树的每个非叶节点只有一个子节点，链表比树的深度长，并且树中的所有节点and 链表都具有相同的值。发生这种情况时，您最终会进行 all 递归调用——您的 if 条件始终得到满足——因此每次您在节点上调用 traverse 时，您在其子节点上调用 traverse 两次。因此，您在根节点上调用 traverse 一次，在其子节点上调用两次，在其孙节点上调用四次，在其曾孙节点上调用八次，等等，即 Θ(2ⁿ)如果有n个节点。

二叉树中的链表

Linked List in Binary Tree

algorithm

binary-tree

linked-list