LeetCode-538

题目

结果

代码

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        rrl(root);
        return root;
    }

    private void rrl(TreeNode node) {
        if (node == null) {
            return;
        }
        rrl(node.right);
        sum += node.val;
        node.val += sum - node.val;
        rrl(node.left);
    }
}

复杂度

时间复杂度：O（n），n为节点个数

空间复杂度：O（n），最坏情况下，数呈现链表状，有n层递归。