首页 > 其他分享 >LeetCode 538. 把二叉搜索树转换为累加树

LeetCode 538. 把二叉搜索树转换为累加树

时间:2023-07-04 22:11:23浏览次数:67  
标签:遍历 cur sum 二叉 LeetCode 累加 节点 538

题目链接:LeetCode 538. 把二叉搜索树转换为累加树

题意:

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

解题思路:

  • 根据二叉搜索树的性质 ,二叉树每个节点看做根节点时,右边分支的每个节点都比根节点大,
  • 左边分支的每个节点都比根节点小。
  • 那么根据题意,我们遍历树的时候,选择反中序遍历,按照右子树 根节点 左子树的次序遍历,并且把遍历到的节点都记录相加。
  • 那么我们遍历到某个节点的时候,能保证大于该节点的节点都已经遍历并且统计完成。
  • 我们只需要修改数值就好了.

代码:


var sum int
func convertBST(root *TreeNode) *TreeNode {
    sum = 0  //sum 表示当前累加的和
    traversal(root)
    return root
}

func traversal(cur *TreeNode) {
    if cur == nil {
        return
    }
    traversal(cur.Right)  //右根左的顺序遍历二叉树
    cur.Val += sum
    sum = cur.Val
    traversal(cur.Left)
}

标签:遍历,cur,sum,二叉,LeetCode,累加,节点,538
From: https://www.cnblogs.com/lxing-go/p/17527159.html

相关文章

  • LeetCode 669. 修剪二叉搜索树
    题目链接:LeetCode669.修剪二叉搜索树题意:给你二叉搜索树的根节点root,同时给定最小边界low和最大边界high。通过修剪二叉搜索树,使得所有节点的值在[low,high]中。修剪树不应该 改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。可以证......
  • LeetCode 235. 二叉搜索树的最近公共祖先
    题目链接:LeetCode235.二叉搜索树的最近公共祖先题意:给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。解题思路:对于二叉搜索树,找两个点的最近公共祖先,这两个点所处的位置只有两种情况:情况一:两点在根节点的左右两侧情况二:两点在根节点的一侧(左侧或者右侧)递归......
  • LeetCode 701. 二叉搜索树中的插入操作
    题目链接:LeetCode701.二叉搜索树中的插入操作题意:给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。解题思路:按照二叉搜索树的定义,直接进行模拟......
  • LeetCode 236. 二叉树的最近公共祖先
    题目链接:LeetCode236.二叉树的最近公共祖先题意:给定一个二叉树,找到该树中两个指定节点的最近公共祖先。解题思路:利用二叉树的后序遍历回溯(从下往上遍历)的思想,依次遍历整个二叉树,在遍历过程中,遇到P就返回p的父节点,遇到q就返回q的父节点,(也就是找到了p,q各自的祖先)......
  • 1043_二叉树的生成和遍历(循环方式)
    1、遍历方法前序遍历(preOrder)对每个节点(子树)、贯彻这个遍历顺序:根->左->右中序遍历(inOrder)左->根->右后序遍历(postOrder)左->右->根层序遍历一层一层、从左到右遍历参考资料:二叉树各种遍历方法递归和循环实现树的层次遍历的几种方法......
  • [leetcode每日一题]7.4
    2679. 矩阵中的和提示中等46相关企业给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空:矩阵中每一行选取最大的一个数,并删除它。如果一行中有多个最大的数,选择任意一个并删除。在步骤1删除的所有数字中找到最大的一个数......
  • (Leetcode)746
    //方式一:第一步不支付费用classSolution{publicintminCostClimbingStairs(int[]cost){intlen=cost.length;int[]dp=newint[len+1];//从下标为0或下标为1的台阶开始,因此支付费用为0dp[0]=0;dp[1]=0;......
  • leetcode 22. 括号生成
    暴力枚举classSolution{publicList<String>generateParenthesis(intn){List<String>list=getAll(2*n);List<String>result=newArrayList<>();for(Stringitem:list){intvalue=0;......
  • 【LeetCode】矩阵中的和
    给你一个下标从0开始的二维整数数组nums。一开始你的分数为0。你需要执行以下操作直到矩阵变为空:矩阵中每一行选取最大的一个数,并删除它。如果一行中有多个最大的数,选择任意一个并删除。在步骤1删除的所有数字中找到最大的一个数字,将它添加到你的分数中。请你返回最......
  • 【笔试实战】LeetCode题单刷题-编程基础 0 到 1【二】
    1822. 数组元素积的符号题目链接1822. 数组元素积的符号题目描述已知函数 signFunc(x) 将会根据 x 的正负返回特定值:如果 x 是正数,返回 1 。如果 x 是负数,返回 -1 。如果 x 是等于 0 ,返回 0 。给你一个整数数组 nums 。令 product 为数组 nums......