Very easy to understand JAVA solution with explanation


  • 0
    A

    The idea is same as inorder . Just that have to do it in the reverse order. Traverse : Right Root Left instead of Left -Root - Right. This is because you need to carry backward the sum of nodes to the smaller nodes. In other words, you are cumulatively adding the value of nodes from the right to the left as the greater to smaller nodes in a BST are arranged in the format Smaller, Greater, Greatest

    public class Solution {
        int prev = 0;
        public TreeNode convertBST(TreeNode root) {
            convertBSTHelper(root);
            return root;
        }
        public void convertBSTHelper (TreeNode root)
        {
            if(root == null) return;
            convertBSTHelper(root.right);
            root.val = root.val + prev;
            prev = root.val;
            convertBSTHelper(root.left);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.