1038.从二叉搜索树到更大和树

链接：1038.从二叉搜索树到更大和树
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

题解 1 - rust

• 编辑时间：2023-12-04
• 内存消耗：2.17MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn bst_to_gst(mut root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut sums = 0;
        fn dfs(node: &mut Option<Rc<RefCell<TreeNode>>>, sums: &mut i32) {
            if let Some(node) = node {
                let mut node_ref = node.as_ref().borrow_mut();
                dfs(&mut node_ref.right, sums);
                *sums += node_ref.val;
                node_ref.val = *sums;
                dfs(&mut node_ref.left, sums);
            }
        }
        dfs(&mut root, &mut sums);
        root
    }
}

题解 2 - cpp

• 编辑时间：2023-12-04
• 内存消耗：8.3MB
• 编程语言：cpp
• 解法介绍：同上。

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int sums = 0;
        function<void(TreeNode*)> dfs = [&](TreeNode *node) {
            if (!node) return;
            dfs(node->right);
            sums += node->val;
            node->val = sums;
            dfs(node->left);
        };
        dfs(root);
        return root;
    }
};

题解 3 - python

• 编辑时间：2023-12-04
• 执行用时：32ms
• 内存消耗：16.11MB
• 编程语言：python
• 解法介绍：利用bst的特性，dfs。

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        sums = 0
        def dfs(node: Optional[TreeNode]):
            nonlocal sums
            if not node: return
            dfs(node.right)
            sums += node.val
            node.val = sums
            dfs(node.left)
        dfs(roo)
        return root