2023-05-10：給你一棵以 root 為根的二叉樹和一個 head 為第一個節點

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

在這裡插入圖檔描述

福大大架構師每日一題java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，雲原生，算法，分布式，網絡，作業系統。501篇原創内容

公衆号