33_把二叉搜索树转换为累加树

简介: 33_把二叉搜索树转换为累加树

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

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

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1:

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

输入:root = [0,null,1]
输出:[1,null,1]

示例 3:

输入:root = [1,0,2]
输出:[3,3,2]

示例 4:

输入:root = [3,2,4,1]
输出:[7,9,4,10]

递归法

class Solution {
   int sum = 0;
   public TreeNode convertBST(TreeNode root) {
       convertBST1(root);
       return root;
   }
   // 按右中左顺序遍历,累加即可
   public void convertBST1(TreeNode root) {
       if (root == null)
           return;
       convertBST(root.right);
       sum += root.val;
       root.val = sum;
       convertBST(root.left);
   }
}
//leetcode submit region end(Prohibit modification and deletion)

迭代法

class Solution {
    //DFS iteration统一迭代法
    public TreeNode convertBST(TreeNode root) {
        int pre = 0;
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) 
            return null;
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();
            //curr!=null的情况,只负责存node到stack中
            if (curr != null) {
                stack.pop();
                if (curr.left != null)  //左
                    stack.add(curr.left);
                stack.add(curr); //中
                stack.add(null);
               if(curr.right != null)      //右
                    stack.add(curr.right);
            }else{
            //curr == null的状况,只负责做单层逻辑
                stack.pop();
                TreeNode temp = stack.pop();
                temp.val += pre;
                pre = temp.val;
            }
        }
        return root;
    }
}
相关文章
|
消息中间件 存储 NoSQL
深入Redis消息队列:Pub/Sub和Stream的对决【redis第六部分】
深入Redis消息队列:Pub/Sub和Stream的对决【redis第六部分】
673 0
|
Java 关系型数据库 数据安全/隐私保护
八股文-面向对象的理解
面向对象编程(Object-Oriented Programming,OOP)是一种程序设计方法,其核心思想是将问题抽象为由若干个对象,通过这些对象之间的调用、配合及协调,共同完成当前的问题。 面向对象的三大基本特征:封装、继承和多态。 面向对象的五大基本原则:单一职责原则、开放封闭原则、里氏替换原则、接口隔离原则、依赖反转原则。
533 1
八股文-面向对象的理解
|
Linux 开发工具 C语言
30天python速成-第一天(python简介及下载安装)
30天python速成-第一天(python简介及下载安装)
|
12月前
|
缓存 JavaScript Oracle
Node.js版本管理工具之NVM
Node.js版本管理工具之NVM
|
12月前
|
SQL Java 关系型数据库
Springboot引入jpa来管理数据库
Springboot引入jpa来管理数据库
241 0
Springboot引入jpa来管理数据库
|
12月前
|
XML 前端开发 Java
Spring,SpringBoot和SpringMVC的关系以及区别 —— 超准确,可当面试题!!!也可供零基础学习
本文阐述了Spring、Spring Boot和Spring MVC的关系与区别,指出Spring是一个轻量级、一站式、模块化的应用程序开发框架,Spring MVC是Spring的一个子框架,专注于Web应用和网络接口开发,而Spring Boot则是对Spring的封装,用于简化Spring应用的开发。
2472 0
Spring,SpringBoot和SpringMVC的关系以及区别 —— 超准确,可当面试题!!!也可供零基础学习
|
领域建模 API 数据安全/隐私保护
DDD的函数式编程实现
【8月更文挑战第16天】
187 0
DDD的函数式编程实现
|
存储 缓存 前端开发
Java八股文面试之多线程篇
Java八股文面试之多线程篇
472 0
Java八股文面试之多线程篇
|
存储 缓存 NoSQL
Redis八股文(大厂面试真题)
Redis八股文(大厂面试真题)
449 1
Redis八股文(大厂面试真题)
|
消息中间件 NoSQL Java
Java知识要点及面试题
该文档涵盖Java后端开发的关键知识点,包括Java基础、JVM、多线程、MySQL、Redis、Spring框架、Spring Cloud、Kafka及分布式系统设计。针对每个主题,文档列举了重要概念及面试常问问题,帮助读者全面掌握相关技术并准备面试。例如,Java基础部分涉及面向对象编程、数据类型、异常处理等;JVM部分则讲解内存结构、类加载机制及垃圾回收算法。此外,还介绍了多线程的生命周期、同步机制及线程池使用,数据库设计与优化,以及分布式系统中的微服务、RPC调用和负载均衡等。
232 0