leetcode538 把二叉搜索树转换成累加树

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

对于每一个点来说，自己的父，和自己父的右子树都是大于自己的。

所以我们按右中左的顺序遍历，每个遍历到的值，比它大的值一定都被遍历过了。

遍历过程中记录和就好。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * public class TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode left;
     
    
   

    

     

    
    

     

       * TreeNode right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 int add = 0;
     
    
   

    

     

    
    

     
 public TreeNode convertBST(TreeNode root) {
     
    
   

    

     

    
    

     
 if (root == null) return root;
     
    
   

    

     

    
    

     

       convertBST(root.right);
     
    
   

    

     

    
    

     

       root.val += add;
     
    
   

    

     

    
    

     

       add = root.val;
     
    
   

    

     

    
    

     

       convertBST(root.left);
     
    
   

    

     

    
    

     
 return root;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103201864