二叉树中的链表

二叉树中的链表(medium)

做题过程

DFS很容易写，但是后面又陷入了分类讨论的思维怪圈，最后又得到了必须要用回溯的结论，实际上从头开始回溯就是枚举了。

算法概述

本题要求为给出一棵树和一个链表，判断树中是否有与链表相同的路径。使用DFS进行枚举。

时间复杂度为：就是枚举
空间复杂度为

JAVA

class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) {
            return false;
        }
        // 主要是这里，从头开始重新调用函数（枚举），没想到
        return dfs(root, head) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    // 这边就简单一些
    public boolean dfs(TreeNode rt, ListNode head) {
        // 链表已经全部匹配完，匹配成功
        if (head == null) {
            return true;
        }
        // 二叉树访问到了空节点，匹配失败
        if (rt == null) {
            return false;
        }
        // 当前匹配的二叉树上节点的值与链表节点的值不相等，匹配失败
        if (rt.val != head.val) {
            return false;
        }
        return dfs(rt.left, head.next) || dfs(rt.right, head.next);
    }
}

总结

主要是return dfs(root, head) || isSubPath(head, root.left) || isSubPath(head, root.right);可以这么写没想到，即用了dfs()函数来进行递归，外部还有一个对isSubPath()的大递归，没想到。