Problem: 538. 把二叉搜索樹轉換為累加樹

題目描述

思路

利用二叉搜索樹中序遍歷的特性，**降序遍歷（此處是想表達先遍歷其右子樹再遍歷其左子樹這樣遍歷的過程中每個節點值得大小排序是降序得）**其節點，然后通過維護一個外部int變量sum求和來修改原始得節點值

復雜度

時間復雜度:

$O(n)$;其中$n$為二叉搜索樹的節點的個數

空間復雜度:

$O(height)$;其中$height$為二叉搜索樹的高度

Code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int sum = 0;/*** Convert BST to Greater Tree** @param root The root of binary tree* @return TreeNode*/public TreeNode convertBST(TreeNode root) {traverse(root);return root;}/*** Convert BST to Greater Tree(Implementation function)** @param root The root of binary tree*/private void traverse(TreeNode root) {if (root == null) {return;}traverse(root.right);sum += root.val;root.val = sum;traverse(root.left);}
}