thảo luận Leetcode mỗi ngày

class Solution {
    int rightSum =0;
    public TreeNode bstToGst(TreeNode root) {
        traverse(root);
        return root;
    }
    private void traverse(TreeNode node){
        if(node==null){
            return;
        }
        traverse(node.right);
        rightSum += node.val;
        node.val = rightSum;
        traverse(node.left);
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def dfs(node, greaterValue):
            if node == None:
                return 0
        
            rightSum = dfs(node.right, greaterValue)
            currentValue = node.val
            node.val = currentValue + rightSum + greaterValue
            leftSum = dfs(node.left, node.val)
            return leftSum + rightSum + currentValue

        dfs(root, 0)
        return root

class Solution {
    func bstToGst(_ root: TreeNode?) -> TreeNode? {

        guard let root = root else { return root }
     
        func dfs(tree: TreeNode, rootValue: Int) -> Int {

            var treeRightValue = 0
            if let right = tree.right {
                treeRightValue += dfs(tree: right, rootValue: rootValue)
            }

            let treeVal = tree.val
            let treeValAndRight = treeVal + treeRightValue
            //let newTreeVal = treeVal + rootValue + treeRightValue
            let newTreeVal = treeValAndRight + rootValue

            var treeLeftValue = 0
            if let left = tree.left {
                treeLeftValue += dfs(tree: left, rootValue: newTreeVal)
            }
            tree.val = newTreeVal
         
            return treeValAndRight + treeLeftValue
        }

        dfs(tree: root, rootValue: 0)

        return root
    }
}

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def gst(node: TreeNode, anchor: int) -> int:
            if not node: return 0
            return gst(node.left, anchor) + \
                gst(node.right, anchor) + \
                (node.val if node.val >= anchor else 0)
        
        def traverse(node: TreeNode, greater_sum: int) -> None:
            if not node: return
            node.val = greater_sum + gst(node, node.val)
            traverse(node.left, node.val)
            traverse(node.right, greater_sum)
        
        traverse(root, 0)
        return root

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.s = 0
        def convert(node):
            if node != None:
                convert(node.right)
                self.s += node.val
                node.val = self.s
                convert(node.left)
        convert(root)
        return root

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {
    private $sumTracking = 0;

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function bstToGst($root) {
        if ($root->val === null) return;

        // calculate for right
        $this->bstToGst($root->right);

        // update value for root
        $this->sumTracking += $root->val;
        $root->val = $this->sumTracking;
        
        // calculate for left
        $this->bstToGst($root->left);

        return $root;
    }
}

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def build(bstNode, ancestorGreaterSum): #return (gstNode, sum of the bstNode's tree)
            if not bstNode:
                return None, 0
            gstNode = TreeNode()

            rightGstNode, rightSum = build(bstNode.right, ancestorGreaterSum)
            gstNode.val = ancestorGreaterSum + bstNode.val + rightSum
            gstNode.right = rightGstNode

            leftGstNode, leftSum = build(bstNode.left, gstNode.val)
            gstNode.left = leftGstNode
            return gstNode, leftSum + rightSum + bstNode.val
        
        return build(root, 0)[0]

class Solution {
    int sum = 0;
    public TreeNode bstToGst(TreeNode root) {
        reverseInorder(root);
        return root;
    }
    public void reverseInorder(TreeNode root){
        if(root==null){
            return;
        }
        reverseInorder(root.right);
        root.val+=sum; 
        sum=root.val;   
        reverseInorder(root.left);
    }
}

var bstToGst = function(root) {
    const dfs = (node) => {
        if (!node) return;

        dfs(node.right);

        right_sum += node.val;
        node.val = right_sum;

        dfs(node.left);
    }

    let right_sum = 0;
    dfs(root);
    return root;
};

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def dfs(root, prev = 0):
            if not root: return prev
            root.val += dfs(root.right, prev)
            return dfs(root.left, root.val)
        dfs(root)
        return root