leetcode538. Convert BST to Greater Tree

本文主要是介绍leetcode538. Convert BST to Greater Tree，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目要求

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:

          5
        /   \
       2     13

Output: The root of a Greater Tree like this:

         18
        /   \
      20     13
   

现有一棵二叉搜索树，需要将二叉搜索树上每个节点的值转化为大于等于该节点值的所有值的和。

思路和代码

这一题可以通过递归的思路来计算出每个节点的目标值。可以知道，每一个节点大于当前节点的值寄存于距离自己最近的左节点以及自己的右节点中。因此计算每个节点时，需要传入当前节点以及距离自己最近的左父节点。

public TreeNode convertBST(TreeNode root) {  
    if (root == null) {  
        return null;  
    }  
    return convertBST(root, null);  
}  
  
public TreeNode convertBST(TreeNode cur, TreeNode leftParent) {  
    TreeNode newCur = new TreeNode(cur.val);  
    if (leftParent != null) {  
        newCur.val += leftParent.val;  
    }  
    if (cur.right != null) {  
        newCur.right = convertBST(cur.right, leftParent);  
        cur.val += cur.right.val;  
        newCur.val += cur.right.val;  
    }  
    if (cur.left != null) {  
        TreeNode newLeft = convertBST(cur.left, newCur);  
        cur.val += cur.left.val;  
        newCur.left = newLeft;  
    }  
    return newCur;  
}

这篇关于leetcode538. Convert BST to Greater Tree的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！