2023-05-10：給你一棵以 root 為根的二叉樹和一個(gè) head 為第一個(gè)節(jié)點(diǎn)的鏈表

如果在二叉樹中，存在一條一直向下的路徑

(資料圖片)

且每個(gè)點(diǎn)的數(shù)值恰好一一對(duì)應(yīng)以 head 為首的鏈表中每個(gè)節(jié)點(diǎn)的值，那么請(qǐng)你返回 True

否則返回 False 。

一直向下的路徑的意思是：從樹中某個(gè)節(jié)點(diǎn)開始，一直連續(xù)向下的路徑。

輸入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]。

輸出：true。

答案2023-05-10：

1.確定鏈表的長(zhǎng)度和節(jié)點(diǎn)值序列。遍歷鏈表，記錄鏈表長(zhǎng)度 n，并將鏈表節(jié)點(diǎn)值存儲(chǔ)到一個(gè)整型數(shù)組 match 中。

2.利用節(jié)點(diǎn)值序列 match 構(gòu)造 KMP 算法中的 next 數(shù)組。next 數(shù)組是為了在匹配過程中能夠快速跳過與前面已匹配部分不相等的情況。

3.將 head 和 root 傳入 isSubPath函數(shù)中計(jì)算是否存在一條向下連續(xù)的路徑恰好對(duì)應(yīng)著鏈表中每個(gè)節(jié)點(diǎn)的值。首先搜索左子樹，將節(jié)點(diǎn)值序列、next 數(shù)組以及當(dāng)前已匹配節(jié)點(diǎn)數(shù) mi 作為參數(shù)傳入 find 函數(shù)中進(jìn)行搜索，若在左子樹中找到解則返回 true，否則再在右子樹中進(jìn)行搜索，直到搜索完整棵樹。

4.在 find 函數(shù)中，若 mi == len(match)，表示已經(jīng)匹配完整個(gè)鏈表，則返回 true；若 cur == nil，表示二叉樹中已沒有可匹配的節(jié)點(diǎn)，返回 false。否則，將當(dāng)前節(jié)點(diǎn)的值與鏈表中未匹配部分的第一個(gè)節(jié)點(diǎn)值比較，如果相等則繼續(xù)往下遞歸，mi + 1 表示已經(jīng)匹配的節(jié)點(diǎn)數(shù)要加 1，否則利用 next 數(shù)組回溯 mi 的值，繼續(xù)比較。直到遞歸結(jié)束返回 true 或 false。

時(shí)間復(fù)雜度：假設(shè)鏈表中的節(jié)點(diǎn)數(shù)為 n，二叉樹的節(jié)點(diǎn)數(shù)為 m，則構(gòu)造 next 數(shù)組的時(shí)間復(fù)雜度是 O(n)，搜索整個(gè)二叉樹的時(shí)間復(fù)雜度是 O(mn)。因此總時(shí)間復(fù)雜度是 O(mn)。

空間復(fù)雜度：除了輸入?yún)?shù)以外，算法使用了常數(shù)個(gè)大小為 n 的數(shù)組和常數(shù)個(gè)遞歸棧空間。因此空間復(fù)雜度是 O(n)。

package mainimport "fmt"http:// Definition for singly-linked list.type ListNode struct {Val  intNext *ListNode}//  Definition for a binary tree node.type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode}func isSubPath(head *ListNode, root *TreeNode) bool {n := 0tmp := headfor tmp != nil {n++tmp = tmp.Next}match := make([]int, n)n = 0tmp = headfor tmp != nil {match[n] = tmp.Valn++tmp = tmp.Next}next := getNextArray(match)return find(root, 0, match, next)}func getNextArray(match []int) []int {if len(match) == 1 {return []int{-1}}next := make([]int, len(match))next[0] = -1next[1] = 0i := 2cn := 0for i < len(next) {if match[i-1] == match[cn] {cn++next[i] = cni++} else if cn > 0 {cn = next[cn]} else {next[i] = 0i++}}return next}func find(cur *TreeNode, mi int, match []int, next []int) bool {if mi == len(match) {return true}if cur == nil {return false}curVal := cur.Valfor mi >= 0 && curVal != match[mi] {mi = next[mi]}return find(cur.Left, mi+1, match, next) || find(cur.Right, mi+1, match, next)}func main() {head := &ListNode{Val: 4,Next: &ListNode{Val: 2,Next: &ListNode{Val:  8,Next: nil,},},}root := &TreeNode{Val: 1,Left: &TreeNode{Val: 4,Right: &TreeNode{Val: 2,Left: &TreeNode{Val:   6,Left:  nil,Right: nil,},Right: &TreeNode{Val:   8,Left:  nil,Right: nil,},},},Right: &TreeNode{Val: 4,Left: &TreeNode{Val:   2,Left:  nil,Right: nil,},Right: &TreeNode{Val: 1,Left: &TreeNode{Val:   3,Left:  nil,Right: nil,},Right: nil,},},}res := isSubPath(head, root)fmt.Println(res) // output: true}

use std::cell::RefCell;use std::rc::Rc;// Definition for singly-linked list.#[derive(PartialEq, Eq, Clone, Debug)]pub struct ListNode {    pub val: i32,    pub next: Option>,}impl ListNode {    #[inline]    fn new(val: i32) -> Self {        ListNode { next: None, val }    }}// Definition for a binary tree node.#[derive(Debug, PartialEq, Eq)]pub struct TreeNode {    pub val: i32,    pub left: Option>>,    pub right: Option>>,}impl TreeNode {    #[inline]    pub fn new(val: i32) -> Self {        TreeNode {            val,            left: None,            right: None,        }    }}fn is_sub_path(head: Option>, root: Option>>) -> bool {    let mut n = 0;    let mut tmp = &head;    while let Some(node) = tmp {        n += 1;        tmp = &node.next;    }    let mut match_arr = Vec::with_capacity(n);    let mut tmp = &head;    while let Some(node) = tmp {        match_arr.push(node.val);        tmp = &node.next;    }    let next = get_next_array(&match_arr);    find(&root, 0, &match_arr, &next)}fn get_next_array(match_arr: &[i32]) -> Vec {    if match_arr.len() == 1 {        return vec![-1];    }    let mut next = vec![0; match_arr.len()];    next[0] = -1;    next[1] = 0;    let mut i = 2;    let mut cn = 0;    while i < next.len() {        if match_arr[i - 1] == match_arr[cn as usize] {            cn += 1;            next[i] = cn;            i += 1;        } else if cn > 0 {            cn = next[cn as usize];        } else {            next[i] = 0;            i += 1;        }    }    next}fn find(cur: &Option>>, mi: usize, match_arr: &[i32], next: &[i32]) -> bool {    if mi == match_arr.len() {        return true;    }    if cur.is_none() {        return false;    }    let cur = cur.as_ref().unwrap().borrow();    let cur_val = cur.val;    let mut mi = mi as i32;    while mi >= 0 && cur_val != match_arr[mi as usize] {        mi = next[mi as usize];    }    find(&cur.left, (mi + 1) as usize, match_arr, next)        || find(&cur.right, (mi + 1) as usize, match_arr, next)}fn main() {    let head = Some(Box::new(ListNode {        val: 4,        next: Some(Box::new(ListNode {            val: 2,            next: Some(Box::new(ListNode { val: 8, next: None })),        })),    }));    let root = Some(Rc::new(RefCell::new(TreeNode {        val: 1,        left: Some(Rc::new(RefCell::new(TreeNode {            val: 4,            left: None,            right: Some(Rc::new(RefCell::new(TreeNode {                val: 2,                left: Some(Rc::new(RefCell::new(TreeNode {                    val: 6,                    left: None,                    right: None,                }))),                right: Some(Rc::new(RefCell::new(TreeNode {                    val: 8,                    left: None,                    right: None,                }))),            }))),        }))),        right: Some(Rc::new(RefCell::new(TreeNode {            val: 4,            left: Some(Rc::new(RefCell::new(TreeNode {                val: 2,                left: None,                right: None,            }))),            right: Some(Rc::new(RefCell::new(TreeNode {                val: 1,                left: Some(Rc::new(RefCell::new(TreeNode {                    val: 3,                    left: None,                    right: None,                }))),                right: None,            }))),        }))),    })));    let res = is_sub_path(head, root);    println!("{}", res); }

#include #include typedef struct ListNode {    int val;    struct ListNode* next;} ListNode;typedef struct TreeNode {    int val;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;int* getNextArray(int* match, int n) {    int* next = (int*)malloc(n * sizeof(int));    if (n == 1) {        next[0] = -1;        return next;    }    next[0] = -1;    next[1] = 0;    int i = 2, cn = 0;    while (i < n) {        if (match[i - 1] == match[cn]) {            next[i++] = ++cn;        }        else if (cn > 0) {            cn = next[cn];        }        else {            next[i++] = 0;        }    }    return next;}int find(TreeNode* cur, int mi, int* match, int* next, int m) {    if (mi == m) {        return 1;    }    if (cur == NULL) {        return 0;    }    int curVal = cur->val;    while (mi >= 0 && curVal != match[mi]) {        mi = next[mi];    }    return find(cur->left, mi + 1, match, next, m) || find(cur->right, mi + 1, match, next, m);}int isSubPath(ListNode* head, TreeNode* root) {    ListNode* tmp = head;    int n = 0;    while (tmp != NULL) {        n++;        tmp = tmp->next;    }    int* match = (int*)malloc(n * sizeof(int));    tmp = head;    int i = 0;    while (tmp != NULL) {        match[i] = tmp->val;        i++;        tmp = tmp->next;    }    int* next = getNextArray(match, n);    int res = find(root, 0, match, next, n);    free(match);    free(next);    return res;}ListNode* newListNode(int x) {    ListNode* node = (ListNode*)malloc(sizeof(ListNode));    node->val = x;    node->next = NULL;    return node;}TreeNode* newTreeNode(int x) {    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));    node->val = x;    node->left = NULL;    node->right = NULL;    return node;}int main() {    ListNode* head = newListNode(4);    head->next = newListNode(2);    head->next->next = newListNode(8);    TreeNode* root = newTreeNode(1);    root->left = newTreeNode(4);    root->right = newTreeNode(4);    root->left->right = newTreeNode(2);    root->right->left = newTreeNode(2);    root->left->right->left = newTreeNode(6);    root->left->right->right = newTreeNode(8);    root->right->left->left = newTreeNode(3);    root->right->left->right = NULL;    int res = isSubPath(head, root);    printf("%d\n", res);    free(head->next->next);    free(head->next);    free(head);    free(root->left->right->right);    free(root->left->right->left);    free(root->left->right);    free(root->left);    free(root->right->left->left);    free(root->right->left);    free(root->right);    free(root);    return 0;}

#include #include using namespace std;struct ListNode {    int val;    ListNode* next;    ListNode(int x) : val(x), next(NULL) {}};struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};vector getNextArray(vector& match) {    vector next(match.size(), 0);    if (match.size() == 1) {        return { -1 };    }    next[0] = -1;    next[1] = 0;    int i = 2;    int cn = 0;    while (i < match.size()) {        if (match[i - 1] == match[cn]) {            cn++;            next[i] = cn;            i++;        }        else if (cn > 0) {            cn = next[cn];        }        else {            next[i] = 0;            i++;        }    }    return next;}bool find(TreeNode* cur, int mi, vector& match, vector& next) {    if (mi == match.size()) {        return true;    }    if (cur == NULL) {        return false;    }    int curVal = cur->val;    while (mi >= 0 && curVal != match[mi]) {        mi = next[mi];    }    return find(cur->left, mi + 1, match, next) || find(cur->right, mi + 1, match, next);}bool isSubPath(ListNode* head, TreeNode* root) {    ListNode* tmp = head;    int n = 0;    while (tmp != NULL) {        n++;        tmp = tmp->next;    }    vector match(n, 0);    tmp = head;    int i = 0;    while (tmp != NULL) {        match[i] = tmp->val;        i++;        tmp = tmp->next;    }    vector next = getNextArray(match);    return find(root, 0, match, next);}int main() {    ListNode* head = new ListNode(4);    head->next = new ListNode(2);    head->next->next = new ListNode(8);    TreeNode* root = new TreeNode(1);    root->left = new TreeNode(4);    root->right = new TreeNode(4);    root->left->right = new TreeNode(2);    root->right->left = new TreeNode(2);    root->left->right->left = new TreeNode(6);    root->left->right->right = new TreeNode(8);    root->right->left->left = new TreeNode(3);    root->right->left->right = NULL;    bool res = isSubPath(head, root);    cout << res << endl;     return 0;}