一个高校的校园网站建设费用,科技公司排名,wordpress文章与页面,wordpress图片链接更换域名版本说明
当前版本号[20231204]。
版本修改说明20231204初版
目录 文章目录 版本说明目录从二叉搜索树到更大和树理解题目代码思路参考代码 原题可以点击此
1038. 从二叉搜索树到更大和树 前去练习。 从二叉搜索树到更大和树
给定一个二叉搜索树 root (BST)#xff0c;请…版本说明
当前版本号[20231204]。
版本修改说明20231204初版
目录 文章目录 版本说明目录从二叉搜索树到更大和树理解题目代码思路参考代码 原题可以点击此
1038. 从二叉搜索树到更大和树 前去练习。 从二叉搜索树到更大和树
给定一个二叉搜索树 root (BST)请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下 二叉搜索树 满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
示例 1 输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]示例 2
输入root [0,null,1]
输出[1,null,1]提示
树中的节点数在 [1, 100] 范围内。0 Node.val 100树中的所有值均 不重复 。
理解题目
1、每个节点的值替换成树中大于或者等于该节点值的所有节点值之和 》
用 4节点 举个例子 比 4节点 大的有 5、6、7、8 节点
所以 4节点 所对应的值 4 5 6 7 8 30
代码思路 它定义了一个名为Solution的类其中包含一个名为bstToGst的方法。该方法接受一个根节点作为参数并返回转换后的累加树的根节点。 def bstToGst(self, root: TreeNode) - TreeNode:在bstToGst方法中定义了一个名为dfs的内部函数用于执行深度优先搜索。该函数接受一个节点作为参数并使用递归的方式遍历整个树。 # 定义一个深度优先搜索函数用于遍历二叉搜索树def dfs(root: TreeNode):在dfs函数中首先声明了一个名为total的变量用于存储当前节点的值加上其左子树中所有节点的值的总和。然后通过递归调用dfs函数遍历右子树将当前节点的值更新为total并将total增加当前节点的值。最后再次递归调用dfs函数遍历左子树。 nonlocal total # 声明total为非局部变量以便在dfs函数内部修改它的值if root:dfs(root.right) # 先遍历右子树total root.val # 累加当前节点的值root.val total # 更新当前节点的值为累加和dfs(root.left) # 再遍历左子树在主函数中初始化了total变量为0然后调用dfs(root)开始遍历整个树。最后返回根节点作为转换后的累加树的根节点。 total 0 # 初始化累加和为0dfs(root) # 调用深度优先搜索函数从根节点开始遍历return root # 返回转换后的二叉搜索树的根节点参考代码
这段代码是一个解决**二叉搜索树BST转换为累加树GST**问题的Python类。
class Solution:def bstToGst(self, root: TreeNode) - TreeNode:def dfs(root: TreeNode):nonlocal totalif root:dfs(root.right)total root.valroot.val totaldfs(root.left)total 0dfs(root)return root
