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

举报
福大大架构师每日一题 发表于 2023/05/10 22:21:24 2023/05/10
【摘要】 2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表如果在二叉树中，存在一条一直向下的路径且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True否则返回 False 。一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。输入：head = [4,2,8], root = [1,4,4,null,2,2,nu...

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

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
二叉树 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入