首页后端开发GO2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m

2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m

时间2023-07-06 06:41:01发布访客分类GO浏览997
导读：2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点每个节点都可以被分配一个从 1 到 n 且互不相同的值另给你一个长度为 m 的数组 queries你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需...

2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点

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

另给你一个长度为 m 的数组 queries

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

从树中 移除 以 queriesi 的值作为根节点的子树

题目所用测试用例保证 queriesi 不 等于根节点的值。

返回一个长度为 m 的数组 answer ，其中 answeri 是执行第 i 个查询后树的高度。

注意：

查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。

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

输入：root = 5,8,9,2,1,3,7,4,6, queries = 3,2,4,8。

输出：3,2,3,2。

答案2023-05-03：

大体过程：

1.定义和初始化全局变量

  • 使用常量 MAXN 定义数组大小。
  • 定义用于深度优先搜索的四个数组 dfn、deep、size、maxl、maxr 和一个计数器 n，保存每个节点的编号、深度、子树大小、左右子树的最大深度。

2.定义深度优先搜索函数 dfs

  • 用一个计数器 i 记录当前节点的编号，并将其存储到数组 dfn 中。
  • 将当前节点的深度 h 存储到数组 deep 中。
  • 将当前节点的子树大小初始化为 1，存储到数组 size 中。
  • 如果当前节点存在左孩子，则递归调用 dfs 函数，并将当前节点的子树大小加上其左孩子的子树大小。
  • 如果当前节点存在右孩子，则递归调用 dfs 函数，并将当前节点的子树大小加上其右孩子的子树大小。

3.在主函数中创建一棵二叉树 root 和一个查询数组 queries。

4.对于每个查询 queries[i]，执行以下操作：

  • 计算以 queries[i] 为根节点的子树编号范围，即 dfn[queries[i]] 到 dfn[queries[i]]+size[dfn[queries[i]]]-1。
  • 将该范围内所有节点的深度保存到数组 maxl 中，并计算其前缀最大值。
  • 将该范围内所有节点的深度保存到数组 maxr 中，并计算其后缀最大值。
  • 计算左右子树的最大深度，取其中的较大值作为删除子树后树的高度。
  • 将结果保存到答案数组 ans 中。

5.返回答案数组。

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

时间复杂度：

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

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

空间复杂度：

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

除了堆栈空间之外，还需要使用常量大小的额外空间来存储全局变量和临时变量，因此总空间复杂度为 O(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]];

    }

}
    

vectorint>
     treeQueries(TreeNode* root, vectorint>
    &
 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 = (int)queries.size();
    
    vectorint>
     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;
    
    vectorint>
 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;

}
在这里插入图片描述

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！

go

若转载请注明出处： 2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m
本文地址： https://pptw.com/jishu/291413.html
ASP.NET Core端点路由中三种让人困惑的路由函数 5.Go语言之配置文件读取学习记录

游客 回复需填写必要信息
↑