本文主要是介绍1038. 从二叉搜索树到更大和树 --力扣 --JAVA,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
给定一个二叉搜索树
root
(BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。提醒一下, 二叉搜索树 满足下列约束条件:
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
解题思路
- 由题意可知需要先获取右子树的值累加再赋值给当前节点,因此使用递归;
- 创建全局变量用来存储累加后的值;
- 右子树是先递归再赋值,左子树需要先赋值再递归,因为左子树的值小于当前节点。
代码展示
class Solution {private int sum = 0;public TreeNode bstToGst(TreeNode root) {if(root == null){return null;}bstToGst(root.right);sum += root.val;//左子树节点的值小于根节点,所以当存在左子树是需要先赋值再递归if(root.left != null){root.val = sum;bstToGst(root.left);} else {root.val = sum;}return root;}
}
这篇关于1038. 从二叉搜索树到更大和树 --力扣 --JAVA的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!