莺时

东边日出西边雨,道是无晴却有晴

Open Source, Open Mind,
Open Sight, Open Future!
  menu
18 文章
3692 浏览
0 当前访客
ღゝ◡╹)ノ❤️

Leetcode 每日抑题 (538. 把二叉搜索树转换为累加树)

LeetCode的每日抑题系列 , LeetCode会每天随机一道题作为签到题。我也是菜鸡,如果今天没A掉,那只能证明我离大神又进了一步。

题目链接

题名 通过率 难度
538. 把二叉搜索树转换为累加树 64.0% 简单
1038. 从二叉搜索树到更大和树 77.4% 中等

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

输入: 原始二叉搜索树: 5是根节点 ; 5.left = 2 ; 5. right = 13

输出: 转换为累加树: 18是根节点 ; 18.left = 20 ; 18. right = 13

解题思路

递归处理 , 先处理右子树,再处理根节点,再处理左子树,二叉搜索树原理就是右子树>根节点>左子树。

需要注意一下两点,虽然题简单,但是稍微一不留神就会漏掉关键东西 . 可以画图

  1. 若右子树的左子树为空,则根节点 = 根节点 + 右子树 ; 若不为空则根节点 = 根节点 + 右子树的最左子节点
  2. 若节点A存在父节点P , 则 A.right = p + A.right .

scala代码

 1import scala.collection.mutable._
 2
 3/**
 4 * 描述:
 5 * ${DESCRIPTION}
 6 *
 7 * @author ludengke
 8 * @create
 9 */
10object Solution3 extends App {
11  def convertBST(root: TreeNode): TreeNode = {
12    if(root !=null){
13      convertBST(root,0)
14    }
15    root
16  }
17
18  /**
19   * 递归处理,先处理右子树,在处理根节点,再处理左子树
20   * @param root
21   * @param num 附加值
22   * @return
23   */
24  def convertBST(root: TreeNode,num: Int): TreeNode = {
25    if(root != null){
26      //递归处理右子树,这是处理当前节点有父节点的情况,num是由处理父节点的函数提供
27      convertBST(root.right,num)
28      if(root.right!=null){
29        //递归找到右子树的最左子节点,这个节点是大于根节点的第一个值
30        var tmp = root.right
31        while(tmp.left!=null){
32          tmp = tmp.left
33        }
34        root.value += tmp.value
35      }else{
36        //如果右子树为空,则value直接加上附加值即可.
37        root.value += num
38      }
39      //递归处理左子树 , 附加值就是根节点的值, 此时根节点的值已经修改过(根据右子树和附加值计算)
40      convertBST(root.left,root.value)
41    }
42    root
43  }
44}
45
46

算法or数据结构

  1. 递归 , 中序遍历的逆向排列(中序遍历成数组,就是有序数组,从尾开始执行num[m-1] = num[m-1] + num[m] ,然后再转化为树)

标题:Leetcode 每日抑题 (538. 把二叉搜索树转换为累加树)
作者:ludengke95
地址:http://xvhi.ludengke95.xyz/articles/2020/09/21/1600668837955.html