2023-05-10：給你一棵以 root 為根的二叉樹和一個 head 為第一個節(jié)點(diǎn)的鏈表 如果在二
2023-05-10：給你一棵以 root 為根的二叉樹和一個 head 為第一個節(jié)點(diǎn)的鏈表
如果在二叉樹中，存在一條一直向下的路徑
且每個點(diǎn)的數(shù)值恰好一一對應(yīng)以 head 為首的鏈表中每個節(jié)點(diǎn)的值，那么請你返回 True
否則返回 False 。
一直向下的路徑的意思是：從樹中某個節(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.確定鏈表的長度和節(jié)點(diǎn)值序列。遍歷鏈表，記錄鏈表長度 n，并將鏈表節(jié)點(diǎn)值存儲到一個整型數(shù)組 match 中。
2.利用節(jié)點(diǎn)值序列 match 構(gòu)造 KMP 算法中的 next 數(shù)組。next 數(shù)組是為了在匹配過程中能夠快速跳過與前面已匹配部分不相等的情況。
3.將 head 和 root 傳入?isSubPath?函數(shù)中計算是否存在一條向下連續(xù)的路徑恰好對應(yīng)著鏈表中每個節(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)匹配完整個鏈表，則返回 true；若 cur == nil，表示二叉樹中已沒有可匹配的節(jié)點(diǎn)，返回 false。否則，將當(dāng)前節(jié)點(diǎn)的值與鏈表中未匹配部分的第一個節(jié)點(diǎn)值比較，如果相等則繼續(xù)往下遞歸，mi + 1 表示已經(jīng)匹配的節(jié)點(diǎn)數(shù)要加 1，否則利用 next 數(shù)組回溯 mi 的值，繼續(xù)比較。直到遞歸結(jié)束返回 true 或 false。
時間復(fù)雜度：假設(shè)鏈表中的節(jié)點(diǎn)數(shù)為 n，二叉樹的節(jié)點(diǎn)數(shù)為 m，則構(gòu)造 next 數(shù)組的時間復(fù)雜度是 O(n)，搜索整個二叉樹的時間復(fù)雜度是 O(mn)。因此總時間復(fù)雜度是 O(mn)。
空間復(fù)雜度：除了輸入?yún)?shù)以外，算法使用了常數(shù)個大小為 n 的數(shù)組和常數(shù)個遞歸棧空間。因此空間復(fù)雜度是 O(n)。
go完整代碼如下：
package?main
import?"fmt"
//?Definition?for?singly-linked?list.
type?ListNode?struct?{
????Val??int
????Next?*ListNode
}
//??Definition?for?a?binary?tree?node.
type?TreeNode?struct?{
????Val???int
????Left??*TreeNode
????Right?*TreeNode
}
func?isSubPath(head?*ListNode,?root?*TreeNode)?bool?{
????n?:=?0
????tmp?:=?head
????for?tmp?!=?nil?{
????????n++
????????tmp?=?tmp.Next
????}
????match?:=?make([]int,?n)
????n?=?0
????tmp?=?head
????for?tmp?!=?nil?{
????????match[n]?=?tmp.Val
????????n++
????????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]?=?-1
????next[1]?=?0
????i?:=?2
????cn?:=?0
????for?i?<?len(next)?{
????????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
}
func?find(cur?*TreeNode,?mi?int,?match?[]int,?next?[]int)?bool?{
????if?mi?==?len(match)?{
????????return?true
????}
????if?cur?==?nil?{
????????return?false
????}
????curVal?:=?cur.Val
????for?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
}
rust完整代碼如下：
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<Box<ListNode>>,
}
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<Rc<RefCell<TreeNode>>>,
????pub?right:?Option<Rc<RefCell<TreeNode>>>,
}
impl?TreeNode?{
????#[inline]
????pub?fn?new(val:?i32)?->?Self?{
????????TreeNode?{
????????????val,
????????????left:?None,
????????????right:?None,
????????}
????}
}
fn?is_sub_path(head:?Option<Box<ListNode>>,?root:?Option<Rc<RefCell<TreeNode>>>)?->?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<i32>?{
????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<Rc<RefCell<TreeNode>>>,?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);?
}
c語言完整代碼如下：
#include?<stdio.h>
#include?<stdlib.h>
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;
}
c++完整代碼如下：
#include?<iostream>
#include?<vector>
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<int>?getNextArray(vector<int>&?match)?{
????vector<int>?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<int>&?match,?vector<int>&?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<int>?match(n,?0);
????tmp?=?head;
????int?i?=?0;
????while?(tmp?!=?NULL)?{
????????match[i]?=?tmp->val;
????????i++;
????????tmp?=?tmp->next;
????}
????vector<int>?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;
}
福大大架構(gòu)師每日一題
java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號
