Java教程
2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，
本文主要是介绍2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表
如果在二叉树中，存在一条一直向下的路径
且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True
否则返回 False 。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
输入：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.确定链表的长度和节点值序列。遍历链表，记录链表长度 n，并将链表节点值存储到一个整型数组 match 中。
2.利用节点值序列 match 构造 KMP 算法中的 next 数组。next 数组是为了在匹配过程中能够快速跳过与前面已匹配部分不相等的情况。
3.将 head 和 root 传入 isSubPath 函数中计算是否存在一条向下连续的路径恰好对应着链表中每个节点的值。首先搜索左子树，将节点值序列、next 数组以及当前已匹配节点数 mi 作为参数传入 find 函数中进行搜索，若在左子树中找到解则返回 true，否则再在右子树中进行搜索，直到搜索完整棵树。
4.在 find 函数中，若 mi == len(match)，表示已经匹配完整个链表，则返回 true；若 cur == nil，表示二叉树中已没有可匹配的节点，返回 false。否则，将当前节点的值与链表中未匹配部分的第一个节点值比较，如果相等则继续往下递归，mi + 1 表示已经匹配的节点数要加 1，否则利用 next 数组回溯 mi 的值，继续比较。直到递归结束返回 true 或 false。
时间复杂度：假设链表中的节点数为 n，二叉树的节点数为 m，则构造 next 数组的时间复杂度是 O(n)，搜索整个二叉树的时间复杂度是 O(mn)。因此总时间复杂度是 O(mn)。
空间复杂度：除了输入参数以外，算法使用了常数个大小为 n 的数组和常数个递归栈空间。因此空间复杂度是 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;
}
这篇关于2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
数据结构与算法面试题详解及练习12-27
-
网络请求面试题详解与实战12-27
-
数据结构和算法面试真题详解与实战教程12-27
-
网络请求面试真题解析与实战教程12-27
-
数据结构和算法大厂面试真题详解与实战指南12-27
-
TS大厂面试真题解析与应对策略12-27
-
TS大厂面试真题详解与解析12-27
-
网站安全入门：如何识别和修复漏洞12-27
-
SQL注入基础教程12-27
-
初学者指南：理解和修复跨域漏洞12-27
-
SQL注入基础知识详解与防范方法12-27
-
SQL注入学习：初学者指南12-27
-
SQL注入学习：初学者指南12-27
-
数据库服务漏洞入门：新手必读指南12-27
-
SQL注入入门：新手必读教程12-27
栏目导航
