LeetCode 把二叉搜索树转换为累加树

第538题

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-bst-to-greater-tree

概念

二叉搜索树

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

中序遍历

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

解题思路

  • 从定义我们知道,BST的中序遍历为一个递增序列
  • 我们将中序遍历倒置(先右子树,后根节点、再左子树),即可实现一个递减序列
  • 遍历该序列,从大往小累加并更新节点值,即可实现累加树(节点值=原来的节点值加上所有大于它的节点值之和)

代码实现

1.递归倒置中序遍历思路实现

//递归实现
class Solution1 {
    public TreeNode convertBST(TreeNode root) {
        addSum(root, 0);
        return root;
    }

    public int addSum(TreeNode node, int parentVal) {
        //如果没有节点了,返回父节点值
        if (node == null) {
            return parentVal;
        }

        //累加右边所有节点值
        int rVal = addSum(node.right, parentVal);

        //当前节点值=右边所有节点累加值+当前节点值
        node.val += rVal;
        //System.out.println("当前节点值:" + node.val);

        //累加左边所有节点值
        int lVal = addSum(node.left, node.val);
        return lVal;
    }
}

2.利用堆栈,去递归化实现

//利用堆栈,去递归化
class Solution2 {
    public TreeNode convertBST(TreeNode root) {
        TreeNode oRoot = root;
        Stack<TreeNode> stack = new Stack();
        int sum = 0;
        while (true) {
            //右节点入栈
            while (root != null) {
                stack.push(root);
                root = root.right;
            }

            //如果栈为空退出循环
            if (stack.empty()) {
                break;
            }
            //否则出栈进入计算
            else {
                TreeNode node = stack.pop();
                //更新节点值
                node.val += sum;
                //更新sum值
                sum = node.val;
                //左节点进入[右节点入栈]
                root = node.left;
            }
        }
        //返回原树,此时该树所有节点已做更新
        return oRoot;
    }
}

总结

我们通过提交代码发现堆栈实现会比递归执行效率慢很多,这是因为:

  • 尾递归被jvm编译器识别并针对其迭代对应进行优化处理过
  • 堆栈实现需要频繁的push(入栈)、pop(出栈)操作导致性能下降

资料

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章