c/c++ leetcode 538.把二叉搜索树转换为累加树

题目描述

难度简单304

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

例如：

输入: 原始二叉搜索树:              5            /   \           2     13输出: 转换为累加树:             18            /   \          20     13

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

解法一.使用递归,反中序遍历

//以从大到小的数进行排列

小的数加上所有比的大的数;

class Solution {public:    int sum = 0;    TreeNode* convertBST(TreeNode* root) {        if  (root == NULL) return NULL;                convertBST(root -> right);        sum += root -> val;        root -> val = sum;        convertBST(root -> left);        return root;    }   };

时空复杂度分析

时间复杂度分析:要遍历整个二叉搜索树,O(N) ; N为树的节点数目;

空间时间复杂度: 最坏情况下开辟N个栈空间为O(N);(二叉树只有右子树或左子树)

解法二,使用stack容器递归

思想与解法一相同;

class Solution {public:    int sum = 0;    TreeNode* convertBST(TreeNode* root) {        if  (root == NULL) return NULL;        TreeNode * curr = root ;        stack
   
     temp;        temp.push(root);        curr = curr -> right;        while (!temp.empty() || curr) {            while (curr) {                temp.push(curr);                curr = curr -> right;            }            curr = temp.top();            temp.pop();            sum += curr -> val;            curr -> val = sum;                 curr = curr -> left;        }        return root ;    }    };