Go
话题列表 社区 Wiki 优质外文 招聘求职 Go 实战教程 社区文档
登录
注册

2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中

moonfdd 的个人博客 / 11 / 0 / 创建于 11个月前

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;
}

在这里插入图片描述

本作品采用《CC 协议》，转载必须注明作者和本文链接
微信公众号：福大大架构师每日一题。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。
moonfdd
1.0k 声望
微信公众号：福大大架构师每日一题。最新面试题，涉及golang，rust，mysq...
讨论数量: 0
排序：
时间 投票
(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！
支持 MD 帮助
moonfdd
未填写
文章
470
粉丝
21
喜欢
37
收藏
22
排名：457
访问：1.9 万
私信
所有博文
文章归档
5 篇 2024 年 4 月 9 篇 2024 年 3 月 3 篇 2024 年 2 月 10 篇 2024 年 1 月 9 篇 2023 年 12 月 9 篇 2023 年 11 月 8 篇 2023 年 10 月 11 篇 2023 年 9 月 14 篇 2023 年 8 月 26 篇 2023 年 7 月 35 篇 2023 年 6 月 51 篇 2023 年 5 月 43 篇 2023 年 4 月 13 篇 2023 年 3 月 15 篇 2023 年 2 月 15 篇 2023 年 1 月 31 篇 2022 年 12 月 30 篇 2022 年 11 月 31 篇 2022 年 10 月 31 篇 2022 年 9 月 30 篇 2022 年 8 月 32 篇 2022 年 7 月 9 篇 2022 年 6 月
最新文章 最受欢迎
2天前 2024-04-17：用go语言，欢迎各位勇者莅临力扣城，本次的挑战游戏名为「力扣泡泡龙」 6天前 2024-04-13：用go语言，给定一个整数数组 `nums`， 请编写一个函数，返回一个新的数组 1周前 2024-04-10：用go语言，考虑一个非负整数数组 A， 如果数组中相邻元素之和为完全平方数 1周前 2024-04-06：用go语言，给你两个非负整数数组 rowSum 和 colSum， 其中 2周前 2024-04-03：用go语言，在一个小城市里，有 m 个房子排成一排， 你需要给每个房子涂上 n 种颜色之一
4 2023-06-19：讲一讲Redis分布式锁的实现？ 3 2022-11-29：查找重复的电子邮箱。以下数据中a@b.com是重复的，请写出sql语句 2 2022-06-22：golang选择题，以下golang代码输出什么？A：3；B：1；C：4；D：编译失败 2 音视频八股文（1）--音视频基础 2 node可以用nvm快速切换版本，golang如何快速切换版本？用gvm就行。
社区赞助商
成为赞助商

关于 LearnKu

LearnKu 是终身编程者的修道场
做最专业、严肃的技术论坛
LearnKu 诞生的故事

资源推荐

  • 《社区使用指南》
  • 《文档撰写指南》
  • 《LearnKu 社区规范》
  • 《提问的智慧》

    • 服务提供商

    其他信息

  • 成为版主
  • 所有测验
  • 联系站长（反馈建议）

    • 粤ICP备18099781号-6 | 粤公网安备 44030502004330号 | 违法和不良信息举报

    由 Summer 设计和编码 ❤

    请登录

    内容举报
    匿名举报，为防止滥用，仅管理员可见举报者。

    我要举报该，理由是：

    取消