【LetMeFly】1038.从二叉搜索树到更大和树:(反)中序遍历
力扣题目链接:https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/
给定一个二叉搜索树 root
(BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
示例 1:
输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:
输入:root = [0,null,1] 输出:[1,null,1]
提示:
注意:该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/ 相同
方法一:(反)中序遍历
二叉搜索树的中序遍历(左子→根→右子
)得到的序列是非递减序列。反之,右子→根→左子
得到的序列就是非递增序列。
“反中序遍历”的过程中,我们只需要使用一个遍历记录“当前所有遍历过的元素的和”,即为大于等于当前元素的所有元素的和。
- 时间复杂度
O
(
n
)
O(n)
n
n
- 空间复杂度
O
(
n
)
O(n)
O
(
n
)
O(n)
AC代码
C++
class Solution {
private:
int last;
void dfs(TreeNode* root) {
if (!root) {
return;
}
dfs(root->right);
last += root->val;
root->val = last;
dfs(root->left);
}
public:
TreeNode* bstToGst(TreeNode* root) {
last = 0;
dfs(root);
return root;
}
};
Python
# from typing import Optional
# # 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 dfs(self, root: Optional[TreeNode]) -> None:
if not root:
return
self.dfs(root.right)
self.last += root.val
root.val = self.last
self.dfs(root.left)
def bstToGst(self, root: TreeNode) -> TreeNode:
self.last = 0
self.dfs(root)
return root
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134782862
原文地址:https://blog.csdn.net/Tisfy/article/details/134782862
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_39056.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!