首页 > 其他 > 详细

力扣练习005---从二叉搜索树到更大和树(1038)

时间:2020-03-14 12:21:51      阅读:59      评论:0      收藏:0      [点我收藏+]

题目描述:

https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/submissions/

 

给出二叉 搜索 树的根节点,该二叉树的节点值各不相同,修改二叉树,使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  节点的左子树仅包含键 小于 节点键的节点。

  节点的右子树仅包含键 大于 节点键的节点。
  左右子树也必须是二叉搜索树。
 

示例:

 技术分享图片

输入:[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]

题目分析:

1、按照二叉搜索树的概念,右子树节点值大于根节点,根节点值大于左子树;

2、很容易想到,本题的关键是用迭代的思想计算本节点和其右子树节点值的和;

3、我的想法是:用中序遍历将二叉树所有节点入栈,然后利用栈的LIFO特性,出栈,并对出栈节点取值累加;

4、不难看出,我的解法可能会耗时和内存占用高一些,后期提交结果来看,确实如此,哈哈哈

Java代码:

public TreeNode bstToGst(TreeNode root) {
    // 中序遍历, 将节点入栈
    Stack<TreeNode> stack = new Stack<>();
    dfs(root, stack);

    int result = 0;
    // 出栈, 结果累加
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result += node.val;
        node.val = result;
    }

    return root;
}

private void dfs(TreeNode root, Stack<TreeNode> stack) {
    if (root == null) {
        return;
    }

    // 左子树
    if (root.left != null) {
        dfs(root.left, stack);
    }

    stack.push(root);

    // 右子树
    if (root.right != null) {
        dfs(root.right, stack);
    }
}

力扣运行结果:

技术分享图片

力扣练习005---从二叉搜索树到更大和树(1038)

原文:https://www.cnblogs.com/sniffs/p/12491063.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!