首页 > 其他分享 >2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，

2023-05-10：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中，存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，

时间：2023-05-10 22:34:24浏览次数：57  
标签：head TreeNode int next 链表 二叉树 root match left

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

在这里插入图片描述

标签：head,TreeNode,int,next,链表,二叉树,root,match,left
From： https://www.cnblogs.com/waitmoon/p/17389539.html

相关文章

  • 学校的数据结构实验_二叉树c语言实现
    二叉树的实现包括二叉树的构建,和二叉树的前中后序便利,二叉树的层序非递归遍历,求二叉树的总结点,求二叉树的最大深度和求二叉树的最大宽度,因为实验主要是对二叉树的各个属性数据测量,所以这里手动链接了一颗二叉树.随后用调用函数接口传参二叉树的根节点测量二叉树的属性.递......
  • 回文链表
    /方法一：反转链表逐个比较/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*///classSolution{//public://boolisPalindrome(ListNode*head){//ListNo......
  • 单链表——追加函数（有无懂的大佬解答一下why不加强制类型过不去）
    #include<bits/stdc++.h>usingnamespacestd;typedefstruct{intid;stringname;}Data;typedefstruct{ DatanodeData; structNode*nextNode;}CLtype;//追加链表CLtype*CLAddEnd(CLtype*head,Datanodedata){CLtype*node,*htemp; if(!(node=(CLt......
  • 968. 监控二叉树
    给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。示例1：输入：[0,0,null,0,0]输出：1解释：如图所示，一台摄像头足以监控所有节点。我的解法classSolution{private:......
  • 双链表和队列-->gcc编译
    双链表队列doublueList.h#include<stdlib.h>#include<stdio.h>#include<assert.h>#include<stdbool.h>typedefintLTDataType;typedefstructDList{ LTDataTypedata; structDList*next; structDList*prev;}LTNode;LTNode*init();......
  • C# WinForm 控件美化之改变ListView Head 的背景色
    方法1：（已测试）给ListView添加以下事件，改实例DataList为控件名称privatevoidDataList_DrawColumnHeader(objectsender,DrawListViewColumnHeaderEventArgse){e.Graphics.FillRectangle(newSolidBrush(Color.Black),e.Bounds);//设置背景颜......
  • 线索化二叉树
    线索化二叉树1.问题分析当对上面的二叉树进行中序遍历时，序列应为：[8,3,10,1,14,6]；但存在一个问题也即，编号为6，8，10，14的几个节点的左右指针并没有完全利用上；如果希望利用到各个节点的左右指针，让各个节点可以指向自己的前后节点，即使用线索化二叉树。2.线索化二叉树基本介绍......
  • 5-9打卡：力扣19. 删除链表的倒数第 N 个结点
    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例1：输入：head=[1,2,3,4,5],n=2输出：[1,2,3,5]示例2：输入：head=[1],n=1输出：[]示例3：输入：head=[1,2],n=1输出：[1] 提示：链表中结点的数目为sz1<=sz<=300<=Node.val<=1001<=n<=sz......
  • 环形链表
     /** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    bool hasCycle(ListNode......
  • 二叉树
    相关知识点：结点拥有的子树数称为结点的度树的度是树内各结点度的最大值树中结点的最大层数称为树的高度或深度 根结点：无双亲，唯一叶结点：无孩子，可以多个中间结点：一个双亲多个孩子 二叉树的特点：每个结点最多有两棵子树左子树和右子树是由顺序的特殊二叉树：斜树，每......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99