上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
}
};
golang 解法, 执行用时: 300 ms, 内存消耗: 30.5 MB, 提交时间: 2023-08-28 10:28:30
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func treeQueries(root *TreeNode, queries []int) []int {
height := map[*TreeNode]int{} // 每棵子树的高度
var getHeight func(*TreeNode) int
getHeight = func(node *TreeNode) int {
if node == nil {
return 0
}
height[node] = 1 + max(getHeight(node.Left), getHeight(node.Right))
return height[node]
}
getHeight(root)
res := make([]int, len(height)+1) // 每个节点的答案
var dfs func(*TreeNode, int, int)
dfs = func(node *TreeNode, depth, restH int) {
if node == nil {
return
}
depth++
res[node.Val] = restH
dfs(node.Left, depth, max(restH, depth+height[node.Right]))
dfs(node.Right, depth, max(restH, depth+height[node.Left]))
}
dfs(root, -1, 0)
for i, q := range queries {
queries[i] = res[q]
}
return queries
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 512 ms, 内存消耗: 184.8 MB, 提交时间: 2023-08-28 10:28:14
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> treeQueries(TreeNode *root, vector<int> &queries) {
unordered_map<TreeNode*, int> height; // 每棵子树的高度
function<int(TreeNode*)> get_height = [&](TreeNode *node) -> int {
return node ? height[node] = 1 + max(get_height(node->left), get_height(node->right)) : 0;
};
get_height(root);
int res[height.size() + 1]; // 每个节点的答案
function<void(TreeNode*, int, int)> dfs = [&](TreeNode *node, int depth, int rest_h) {
if (node == nullptr) return;
++depth;
res[node->val] = rest_h;
dfs(node->left, depth, max(rest_h, depth + height[node->right]));
dfs(node->right, depth, max(rest_h, depth + height[node->left]));
};
dfs(root, -1, 0);
for (auto &q : queries) q = res[q];
return queries;
}
};
java 解法, 执行用时: 73 ms, 内存消耗: 69.8 MB, 提交时间: 2023-08-28 10:27:53
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Map<TreeNode, Integer> height = new HashMap<>(); // 每棵子树的高度
private int[] res; // 每个节点的答案
public int[] treeQueries(TreeNode root, int[] queries) {
getHeight(root);
height.put(null, 0); // 简化 dfs 的代码，这样不用写 getOrDefault
res = new int[height.size()];
dfs(root, -1, 0);
for (var i = 0; i < queries.length; i++)
queries[i] = res[queries[i]];
return queries;
}
private int getHeight(TreeNode node) {
if (node == null) return 0;
var h = 1 + Math.max(getHeight(node.left), getHeight(node.right));
height.put(node, h);
return h;
}
private void dfs(TreeNode node, int depth, int restH) {
if (node == null) return;
++depth;
res[node.val] = restH;
dfs(node.left, depth, Math.max(restH, depth + height.get(node.right)));
dfs(node.right, depth, Math.max(restH, depth + height.get(node.left)));
}
}
python3 解法, 执行用时: 1080 ms, 内存消耗: 84.7 MB, 提交时间: 2023-08-28 10:27:39
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
height = defaultdict(int) # 每棵子树的高度
def get_height(node: Optional[TreeNode]) -> int:
if node is None: return 0
height[node] = 1 + max(get_height(node.left), get_height(node.right))
return height[node]
get_height(root)
res = [0] * (len(height) + 1) # 每个节点的答案
def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:
if node is None: return
depth += 1
res[node.val] = rest_h
dfs(node.left, depth, max(rest_h, depth + height[node.right]))
dfs(node.right, depth, max(rest_h, depth + height[node.left]))
dfs(root, -1, 0)
for i, q in enumerate(queries):
queries[i] = res[q]
return queries
