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

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

时间:2023-05-03 22:32:35浏览次数:52  
标签:03 head TreeNode int dfn MAXN 二叉树 queries 节点

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

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

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

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

从树中 移除 以 queries[i] 的值作为根节点的子树

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

返回一个长度为 m 的数组 answer ,其中 answer[i] 是执行第 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 定义数组大小。
  • 定义用于深度优先搜索的四个数组 dfndeepsizemaxlmaxr 和一个计数器 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 函数中,需要处理 2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行_数组 个查询,对于每个查询需要计算左右子树的最大深度,时间复杂度为 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)
}

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

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

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

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 = (int)queries.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 你必须在树上执行_子树_04

标签:03,head,TreeNode,int,dfn,MAXN,二叉树,queries,节点
From: https://blog.51cto.com/u_14891145/6241572

相关文章

  • 2023-05-03 线性模型与区间DP
    线性模型与区间DP1线性模型基本概念这里的线性是指状态的排布是线性的线性模型是动态规划中最常用的模型一般的代码模型是:for(inti=0;i<n;i++){for(j=0;j<i;j++){//Todo:更新dp的具体逻辑}}最典型的一个例题:最长上升子序列见第......
  • 力扣---1003. 检查替换后的词是否有效
    给你一个字符串s,请你判断它是否有效。字符串s有效需要满足:假设开始有一个空字符串t="",你可以执行任意次下述操作将t转换为s:将字符串"abc"插入到t中的任意位置。形式上,t变为tleft+"abc"+tright,其中t==tleft+tright。注意,tleft和tright可能为......
  • 2023-05-03:给你一棵 二叉树 的根节点 root ,树中有 n 个节点 每个节点都可以被分配一个
    2023-05-03:给你一棵二叉树的根节点root,树中有n个节点每个节点都可以被分配一个从1到n且互不相同的值另给你一个长度为m的数组queries你必须在树上执行m个独立的查询,其中第i个查询你需要执行以下操作:从树中移除以queries[i]的值作为根节点的子树题目所......
  • 算导03
     ......
  • 每日总结2023-05-03
    今天学习了Android中的数据传递: 发送://实例化一个新的窗口,并指定从那个窗口到哪个窗口intent=newIntent(MainActivity.this,secondwindow.class);//将数据发送到intent中intent.putExtra("name",ed_text.getText().toString().trim());//启动新窗口startActivity(in......
  • 关于AWS-ElastiCache-的Reserved_Cache_Nodes-预留节点-是没有多可用区的概念的
    今天在整理完善一个关于所有AWS账号的ElastiCache-的RN信息表格时,发现有一个字段要求写是否是多可用区笔者之前还没有注意过关于ElastiCache的RN的多可用区的问题,不过,像RDS确实有这个概念于是笔者去ElastiCache的 Purchasereservednodes界面又再次确认了一下,确实没有多可用......
  • 【23.05.03】好题题解
    好题题解A题目大意:计算一个项数为\(n\)的多项式除以\(x^3-x\)的余数多项式。数据范围:对于\(100\%\)的数据:\(2\leqn\leq2\times10^5\)解题分析:水题,直接多项式除法模拟即可。需要注意细节。ACCode:#include<bits/stdc++.h>usingnamespacestd;#d......
  • 【实变函数】03 - 可测函数
    上篇在\(\sigma\)-环上延拓了测度的概念,并讨论了实数轴上典型的可测集\(\mathbf{L},\mathbf{L^g},\mathbf{B}\)。这些理论精巧而有其独立性,但还需放到合适的领域里才能展现其本质和威力。\(\sigma\)-环是个普遍的代数结构,它的可列交并运算特别适用于需要级数运算的场合,这也将......
  • Ruby安装错误:in `encode': U+00CD to IBM437 in conversion from UTF-16LE to UTF-8 t
    解决方法:去本地路径下修改编码,这么提示是因为编码不一致导致的。  修改registry文件中的编码:  修改后就没有问题了。 来源:https://www.cnblogs.com/py-tiger/p/5372258.html......
  • 1159 Structure of a Binary Tree + 根据前序和中序构建二叉树+ 层序遍历模板复习
    题目链接:https://pintia.cn/problem-sets/994805342720868352/exam/problems/1478635126488367104唉,今天的bug出在了下面这条语句。if(tree[root_key].left*tree[root_key].right<0)full_tree=false;我写成了full_tree=!(tree[root_key].left*tree[root_key].rig......