Sword finger offer II 054. Sum of all values greater than or equal to nodes (medium binary search tree DFS)

The finger of the sword Offer II 054. Sum of all values greater than or equal to nodes

Given a binary search tree , Please replace the value of each node with the sum of all node values greater than or equal to the node value in the tree .

As a reminder , The binary search tree satisfies the following constraints ：

The left subtree of a node contains only the key Less than Node key node .
The right subtree of a node contains only the key Greater than Node key node .
Left and right subtrees must also be binary search trees .

Example 1：

Input ：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output ：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2：

Input ：root = [0,null,1]
Output ：[1,null,1]
Example 3：

Input ：root = [1,0,2]
Output ：[3,3,2]
Example 4：

Input ：root = [3,2,4,1]
Output ：[7,9,4,10]

Tips ：

The number of nodes in the tree is between 0 and 104 Between .
The value of each node is between -104 and 104 Between .
All the values in the tree Different from each other .
The given tree is a binary search tree .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/w6cpku
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

utilize dfs Traversing the tree , The direction of traversal is Right -> in -> Left , Contrary to normal post order traversal , use sum Record the sum of all nodes starting from the node in the lower right corner , And re assign values to all nodes .

Answer key （Java）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
    
        if (root != null) {
    
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}