技术教程 编程代码 2023-05-03：给你一棵 二叉树 的根节点 root ，树中有 n 个节点 每个节点都可以被分配一个从 1 到 n 且互不相同的值 另给你一个长度为 m 的数组 queries 你必须在树上执行 正文

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

2023-07-29,,

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 定义数组大小。

定义用于深度优先搜索的四个数组 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]];

    }

}

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 你必须在树上执行的相关教程结束。

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

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!