网站建设能做什么工作,工商管理局注册查询,网站制作与app开发哪个要难一点,南昌集团网站建设公司题目链接
把二叉搜索树转换为累加树
题目描述 注意点
树中的节点数介于 0 和 10000 之间每个节点的值介于 -10000 和 10000 之间树中的所有值 互不相同给定的树为二叉搜索树
解答思路
因为二叉搜索树的性质是左子树的值始终小于根节点的值#xff0c;右子树的值始终大于根…题目链接
把二叉搜索树转换为累加树
题目描述 注意点
树中的节点数介于 0 和 10000 之间每个节点的值介于 -10000 和 10000 之间树中的所有值 互不相同给定的树为二叉搜索树
解答思路
因为二叉搜索树的性质是左子树的值始终小于根节点的值右子树的值始终大于根节点的值对于任意一个节点其右子树的累加和为右子树下节点的累加和根节点的累加和为右子树的累加和再加上根节点的值左子树的累加和为根节点的累加和再加上左子树下节点的累加和本题是要找到比当前节点大于或等于的数值之和其决定关系为右子树-根节点-左子树所以本题使用反向中序遍历也就是先遍历右子树再遍历根节点最后遍历左子树
代码
class Solution {int sum 0;public TreeNode convertBST(TreeNode root) {if (root ! null) {convertBST(root.right);sum root.val;root.val sum;convertBST(root.left);}return root;}
}关键点
各节点的累加和的推理关系为右子树-根节点-左子树递归遍历二叉树
