> 科技资讯 > 2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行

2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行

科技资讯 投稿 6200℃ 0 评论

2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行

每个节点都可以被分配一个从 1 到 n 且互不相同的值

你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：

题目所用测试用例保证 queries[i] 不 等于根节点的值。

注意：

树的高度是从根到树中某个节点的 最长简单路径中的边数 。

输出：[3,2,3,2]。

大体过程：

    使用常量 MAXN 定义数组大小。

  • dfn、deep、size、maxl、maxr 和一个计数器 n，保存每个节点的编号、深度、子树大小、左右子树的最大深度。

dfs

    i 记录当前节点的编号，并将其存储到数组 dfn 中。

  • h 存储到数组 deep 中。

  • size 中。

  • dfs 函数，并将当前节点的子树大小加上其左孩子的子树大小。

  • dfs 函数，并将当前节点的子树大小加上其右孩子的子树大小。

root 和一个查询数组 queries。

queries[i]，执行以下操作：

    queries[i] 为根节点的子树编号范围，即 dfn[queries[i]] 到 dfn[queries[i]]+size[dfn[queries[i]]]-1。

  • maxl 中，并计算其前缀最大值。

  • maxr 中，并计算其后缀最大值。

  • 将结果保存到答案数组 ans 中。

注意：在每次查询中，需要重新计算左右子树的最大深度，因为每次查询都会修改树的结构。

在 dfs 函数中，对于每个节点最多访问一次，因此该函数的时间复杂度为 O(n，其中 n 是二叉树的节点数。

treeQueries 函数中，需要处理 $m$ 个查询，对于每个查询需要计算左右子树的最大深度，时间复杂度为 O(n，因此总时间复杂度为 O(mn。

在 C++ 中，数组和变量的空间占用量是固定的，因此空间复杂度主要取决于递归调用时堆栈的空间占用量。由于最坏情况下二叉树可能退化成一个链表，因此堆栈空间的最大使用量为 O(n，其中 n 是二叉树的节点数。

go完整代码如下：

package main

import (
	"fmt"


type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

const MAXN = 100010

var dfn [MAXN]int
var deep [MAXN]int
var size [MAXN]int
var maxl [MAXN]int
var maxr [MAXN]int
var n int

func treeQueries(root *TreeNode, queries []int []int {
	n = 0
	dfs(root, 0
	for i := 1; i <= n; i++ {
		maxl[i] = max(maxl[i-1], deep[i]
	}
	maxr[n+1] = 0
	for i := n; i >= 1; i-- {
		maxr[i] = max(maxr[i+1], deep[i]
	}
	m := len(queries
	ans := make([]int, m
	for i := 0; i < m; i++ {
		leftMax := maxl[dfn[queries[i]]-1]
		rightMax := maxr[dfn[queries[i]]+size[dfn[queries[i]]]]
		ans[i] = max(leftMax, rightMax
	}
	return ans
}

func dfs(head *TreeNode, h int {
	i := n + 1
	dfn[head.Val] = i
	deep[i] = h
	size[i] = 1
	n = i
	if head.Left != nil {
		dfs(head.Left, h+1
		size[i] += size[dfn[head.Left.Val]]
	}
	if head.Right != nil {
		dfs(head.Right, h+1
		size[i] += size[dfn[head.Right.Val]]
	}
}

func max(a, b int int {
	if a > b {
		return a
	}
	return b
}

func main( {
	root := &TreeNode{
		Val: 5,
		Left: &TreeNode{
			Val: 8,
			Left: &TreeNode{
				Val:   2,
				Left:  nil,
				Right: nil,
			},
			Right: &TreeNode{
				Val:   9,
				Left:  nil,
				Right: nil,
			},
		},
		Right: &TreeNode{
			Val: 3,
			Left: &TreeNode{
				Val:   1,
				Left:  nil,
				Right: nil,
			},
			Right: &TreeNode{
				Val: 7,
				Left: &TreeNode{
					Val:   4,
					Left:  nil,
					Right: nil,
				},
				Right: &TreeNode{
					Val:   6,
					Left:  nil,
					Right: nil,
				},
			},
		},
	}
	queries := []int{3, 2, 4, 8}
	ans := treeQueries(root, queries
	fmt.Println("The query results are:", ans
}

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100010

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int dfn[MAXN];
int deep[MAXN];
int size[MAXN];
int maxl[MAXN];
int maxr[MAXN];
int n;

int max0(int a, int b {
    return a > b ? a : b;
}

void dfs(struct TreeNode* head, int h;
int* treeQueries(struct TreeNode* root, int* queries, int queriesSize, int* returnSize;

int main( {
    struct TreeNode node9 = { 9, NULL, NULL };
    struct TreeNode node8 = { 8, NULL, &node9 };
    struct TreeNode node2 = { 2, NULL, NULL };
    struct TreeNode node4 = { 4, NULL, NULL };
    struct TreeNode node1 = { 1, NULL, NULL };
    struct TreeNode node6 = { 6, NULL, NULL };
    struct TreeNode node7 = { 7, &node4, &node6 };
    struct TreeNode node3 = { 3, &node1, &node7 };
    struct TreeNode node5 = { 5, &node8, &node3 };
    struct TreeNode* root = &node5;
    int queries[] = { 3, 2, 4, 8 };
    int queriesSize = sizeof(queries / sizeof(int;
    int returnSize = 0;
    int* ans = treeQueries(root, queries, queriesSize, &returnSize;
    printf("The query results are: [";
    for (int i = 0; i < returnSize; i++ {
        if (i > 0 {
            printf(", ";
        }
        printf("%d", ans[i];
    }
    printf("]\n";
    free(ans;
    return 0;
}

void dfs(struct TreeNode* head, int h {
    int i = ++n;
    dfn[head->val] = i;
    deep[i] = h;
    size[i] = 1;
    if (head->left != NULL {
        dfs(head->left, h + 1;
        size[i] += size[dfn[head->left->val]];
    }
    if (head->right != NULL {
        dfs(head->right, h + 1;
        size[i] += size[dfn[head->right->val]];
    }
}

int* treeQueries(struct TreeNode* root, int* queries, int queriesSize, int* returnSize {
    n = 0;
    dfs(root, 0;
    int i;
    for (i = 1; i <= n; i++ {
        maxl[i] = max0(maxl[i - 1], deep[i];
    }
    maxr[n + 1] = 0;
    for (i = n; i >= 1; i-- {
        maxr[i] = max0(maxr[i + 1], deep[i];
    }
    int* ans = (int*malloc(queriesSize * sizeof(int;
    for (i = 0; i < queriesSize; i++ {
        int leftMax = maxl[dfn[queries[i]] - 1];
        int rightMax = maxr[dfn[queries[i]] + size[dfn[queries[i]]]];
        ans[i] = max0(leftMax, rightMax;
    }
    *returnSize = queriesSize;
    return ans;
}

c++完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x : val(x, left(nullptr, right(nullptr {}
};

const int MAXN = 100010;
int dfn[MAXN];
int deep[MAXN];
int size0[MAXN];
int maxl[MAXN];
int maxr[MAXN];
int n;

void dfs(TreeNode* head, int h {
    int i = ++n;
    dfn[head->val] = i;
    deep[i] = h;
    size0[i] = 1;
    if (head->left != nullptr {
        dfs(head->left, h + 1;
        size0[i] += size0[dfn[head->left->val]];
    }
    if (head->right != nullptr {
        dfs(head->right, h + 1;
        size0[i] += size0[dfn[head->right->val]];
    }
}

vector<int> treeQueries(TreeNode* root, vector<int>& queries {
    n = 0;
    dfs(root, 0;
    for (int i = 1; i <= n; i++ {
        maxl[i] = max(maxl[i - 1], deep[i];
    }
    maxr[n + 1] = 0;
    for (int i = n; i >= 1; i-- {
        maxr[i] = max(maxr[i + 1], deep[i];
    }
    int m = (intqueries.size(;
    vector<int> ans(m;
    for (int i = 0; i < m; i++ {
        int leftMax = maxl[dfn[queries[i]] - 1];
        int rightMax = maxr[dfn[queries[i]] + size0[dfn[queries[i]]]];
        ans[i] = max(leftMax, rightMax;
    }
    return ans;
}

int main( {
    TreeNode node9(9;
    TreeNode node8(8;
    node8.right = &node9;
    TreeNode node2(2;
    TreeNode node4(4;
    TreeNode node1(1;
    TreeNode node6(6;
    TreeNode node7(7;
    node7.left = &node4;
    node7.right = &node6;
    TreeNode node3(3;
    node3.left = &node1;
    node3.right = &node7;
    TreeNode node5(5;
    node5.left = &node8;
    node5.right = &node3;
    vector<int> queries{ 3, 2, 4, 8 };
    auto ans = treeQueries(&node5, queries;
    cout << "The query results are: [";
    for (int i = 0; i < ans.size(; i++ {
        if (i > 0 {
            cout << ", ";
        }
        cout << ans[i];
    }
    cout << "]" << endl;
    return 0;
}

编程笔记 » 2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行

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

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