1038. 从二叉搜索树到更大和树 --力扣 --JAVA

简介: 给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。提醒一下, 二叉搜索树 满足下列约束条件:节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。

 题目

给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

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

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

    解题思路

      1. 由题意可知需要先获取右子树的值累加再赋值给当前节点,因此使用递归;
      2. 创建全局变量用来存储累加后的值;
      3. 右子树是先递归再赋值,左子树需要先赋值再递归,因为左子树的值小于当前节点。

      代码展示

      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;
          }
      }

      image.gif


      目录
      相关文章
      |
      7天前
      |
      Java
      LeetCode题解-逆波兰表达式求值-Java
      逆波兰表达式求值-Java
      6 0
      |
      7天前
      |
      Java
      |
      7天前
      |
      Java
      |
      7天前
      |
      Java
      LeetCode题解-二叉搜索树中第K小的元素-Java
      LeetCode题解-二叉搜索树中第K小的元素-Java
      6 0
      |
      7天前
      |
      Java
      |
      7天前
      LeetCode 树-简单题 4个典例
      LeetCode 树-简单题 4个典例
      11 0
      |
      7天前
      |
      Java
      LeetCode题解- 两两交换链表中的节点-Java
      两两交换链表中的节点-Java
      7 0
      |
      7天前
      |
      Java
      LeetCode题解-合并K个有序数组-Java
      合并K个有序数组-Java
      5 0
      |
      7天前
      |
      Java
      |
      7天前
      |
      Java
      LeetCode-电话号码的字母组合-Java
      电话号码的字母组合-Java
      6 0

      热门文章

      最新文章

      相关产品

    1. 云迁移中心