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

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

科技资讯 投稿 6600℃ 0 评论

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

如果在二叉树中，存在一条一直向下的路径

否则返回 False 。

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]。

答案2023-05-10：

大体步骤如下：

2.利用节点值序列 match 构造 KMP 算法中的 next 数组。next 数组是为了在匹配过程中能够快速跳过与前面已匹配部分不相等的情况。

isSubPath 函数中计算是否存在一条向下连续的路径恰好对应着链表中每个节点的值。首先搜索左子树，将节点值序列、next 数组以及当前已匹配节点数 mi 作为参数传入 find 函数中进行搜索，若在左子树中找到解则返回 true，否则再在右子树中进行搜索，直到搜索完整棵树。

时间复杂度：假设链表中的节点数为 n，二叉树的节点数为 m，则构造 next 数组的时间复杂度是 O(n，搜索整个二叉树的时间复杂度是 O(mn。因此总时间复杂度是 O(mn。

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 为首的链表中每个节点的值

赞同 (33) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽