1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  public boolean isSubPath(ListNode head, TreeNode root) {
    if(head == null) return true;//鏈表跑到null，代表整個鏈表都跑完，都有配對到
    if(root == null) return false;//樹跑完，但鏈表沒跑完，代表不相同
    if(isSame(head, root))//判斷鏈表與tree是不是一樣的
      return true;
    return isSubPath(head, root.left) || isSubPath(head, root.right);//不是就比較左子樹 或 右子樹 有沒有存在跟鏈表相同的值
  }
  private boolean isSame(ListNode head, TreeNode root) {
    if(head == null) return true;//鏈表跑到null，代表整個鏈表都跑完，都有配對到
    if(root == null) return false;//樹跑完，但鏈表沒跑完，代表不相同
    if(head.val != root.val)
      return false;
    return isSame(head.next, root.left) || isSame(head.next, root.right);//把鏈表的下一個值與左右子樹比一比
  }
}