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

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

题目链接

给定一个二叉搜索树（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 代码

import scala.collection.mutable._

/**
 * 描述:
 * ${DESCRIPTION}
 *
 * @author ludengke
 * @create
 */
object Solution3 extends App {
  def convertBST(root: TreeNode): TreeNode = {
    if(root !=null){
      convertBST(root,0)
    }
    root
  }

  /**
   * 递归处理,先处理右子树,在处理根节点,再处理左子树
   * @param root
   * @param num 附加值
   * @return
   */
  def convertBST(root: TreeNode,num: Int): TreeNode = {
    if(root != null){
      //递归处理右子树,这是处理当前节点有父节点的情况,num是由处理父节点的函数提供
      convertBST(root.right,num)
      if(root.right!=null){
        //递归找到右子树的最左子节点,这个节点是大于根节点的第一个值
        var tmp = root.right
        while(tmp.left!=null){
          tmp = tmp.left
        }
        root.value += tmp.value
      }else{
        //如果右子树为空,则value直接加上附加值即可.
        root.value += num
      }
      //递归处理左子树 , 附加值就是根节点的值, 此时根节点的值已经修改过(根据右子树和附加值计算)
      convertBST(root.left,root.value)
    }
    root
  }
}

算法 or 数据结构

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