Leetcode538. 把二叉搜索树转换为累加树c++实现

题目描述

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

分析

首先，二叉搜索树按照中序遍历的序列是单调的，这里用一个栈来存储中序遍历的结果，边遍历边累加。

代码实现

  /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* convertBST(TreeNode* root) {
            stack<TreeNode*> mystack; 
            TreeNode* cur = root; 
            int add = 0; 
            while(cur != NULL || !mystack.empty())
            {
                if(cur != NULL)
                {
                    mystack.push(cur);
                    cur = cur->right;
                }
                else 
                {
                    cur = mystack.top();
                    mystack.pop();
                    cur->val += add;
                    add = cur->val;
                    cur = cur->left;
                }
            }
            return root; 
        } 
    };

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_35091252/article/details/90739945
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-25 02:28:52

阅读 ( 923 )