1
2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，
作者：福大大架构师每日一题
- 2023-05-10 北京
本文字数：6086 字
阅读完需：约 20 分钟
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;}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/39e3ca4b57650babf6307c260】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
评论