49-分割链表

49-二叉树中的列表

不会做。

参考做法

算法思想

迭代，就是挨个试二叉树的节点，看从此结点开始是否有与head相一致的路径。

一个递归函数 isSub。

参数：当前匹配到的二叉树节点tn,当前匹配到的链表节点ln。

返回值：该节点是否匹配，匹配为true，否则为false。

有四种情况：

1. ln为空，即链表节点为空，说明全部匹配完了，返回true
2. tn为空，说明二叉树节点为空，但链表节点不为空，返回false
3. tn->val != ln->val，返回false
4. 如果上述三种情况都不满足，说明当前待匹配二叉树节点和链表节点是匹配的，那么就看该二叉树节点的左子节点和链表下一个节点是否匹配，或右子结点和链表下一个节点是否匹配。只要有一个匹配即可，所有用或符号||连接。

在主函数中，不断迭代二叉树节点，即尝试以每个二叉树节点为根的树是否有这样一条路径。且只要有一个子树有就可以。

算法实现

class Solution {
public:

    bool isSub(TreeNode * tn, ListNode * ln) {
        //链表为空，说明匹配完了，返回ture
        if(ln == nullptr) {
            return true;
            //二叉树为空，返回false
        } else if(tn == nullptr) {
            return false;
        } else if(tn->val != ln->val) {
            return false;
        } else {
            return isSub(tn->left, ln->next) || isSub(tn->right, ln->next);
        }
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        if(root == nullptr) {
            return false;
        }
        if(head == nullptr) {
            return true;
        }
        //分别尝试以当前二叉树节点为根的树、以该节点的左子结点和右子结点为根的树是否有这样一条路径。
        // 只要有一个子树有就可以，所以使用或符号
        return isSub(root, head) || isSubPath(head, root->left)
        || isSubPath(head, root->right);
    }
};

性能分析

时间复杂度：每个子树最多匹配*min($2^{len + 1}$, n)*次，len是链表长度。若该二叉树共有n个节点，则最坏情况需要：

​ $O(n * min(2^{len + 1}, n))$。

空间复杂度：$O(height)$，height为二叉树高度。