【树】538. 把二叉搜索树转换为累加树

Tips 2020-05-03

题目:

【树】538. 把二叉搜索树转换为累加树

解答:

方法一:回溯

想法:

一个反序中序遍历的方法是通过递归实现。通过调用栈回到之前的节点,我们可以轻松地反序遍历所有节点。

算法:

在递归方法中,我们维护一些递归调用过程中可以访问和修改的全局变量。首先我们判断当前访问的节点是否存在,如果存在就递归右子树,递归回来的时候更新总和和当前点的值,然后递归左子树。如果我们分别正确地递归 root.right 和 root.left ,那么我们就能正确地用大于某个节点的值去更新此节点,然后才遍历比它小的值。

时间复杂度:O(N)

空间复杂度:O(N)

/**
 * 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) 
    {
        if (root != NULL) 
        {
            convertBST(root->right);

            sum += root->val;
            root->val = sum;

            convertBST(root->left);
        }
        return root;
    }
private:
    int sum = 0;
};

方法二:使用栈迭代 [Accepted]

想法:

如果我们不想使用递归,我们可以通过迭代和栈来实现函数调用栈的过程。

算法:

一个描述迭代栈的方法就是通过递归的思想。首先我们初始化一个空的栈并把根节点作为当前节点。然后只要在栈中有未遍历节点或者 node 节点不为空,我们就将当前节点到最右边叶子路径上的点全部压入栈中。这与递归过程中我们总是先走右子树的思路是一致的,这个思路确保我们总是降序遍历所有节点的值。接下来,我们访问栈顶节点,并考虑它的左子树,这就像我们递归中先遍历当前节点再遍历它的左子树的思路。最后,我们的栈为空并且 node 指向树中最小节点的左孩子 null ,循环结束。

/**
 * 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) 
    {
        int sum = 0;
        TreeNode *node = root;
        stack<TreeNode*> st;

        while (!st.empty() || node != NULL)
        {
            /* push all nodes up to (and including) this subtree‘s maximum on
             * the stack. */
            while (node != NULL)
            {
                st.push(node);
                node = node->right;
            }

            node = st.top();
            st.pop();
            sum += node->val;
            node->val = sum;

            /* all nodes with values between the current and its parent lie in
             * the left subtree. */
            node = node->left;
        }

        return root;
    }
};

相关推荐