专栏首页机器学习入门LeetCode Weekly Contest 24 之 538.Convert BST to Greater Tree

LeetCode Weekly Contest 24 之 538.Convert BST to Greater Tree

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/63687692

LeetCode Weekly Contest 24

赛题

本次周赛主要分为一下4道题:

  • 543 Diameter of Binary Tree (4分)
  • 538 Convert BST to Greater Tree (6分)
  • 542 01 Matrix (7分)
  • 544 Output Contest Matches (7分)

538 Convert BST to Greater Tree

Problem:

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:

唉,这道题我是没有解出来,把简单的问题想复杂了。如果能够准确理解题目的意思,那么思路也就出来了,也是一道DFS题。先来看看解决方案吧,否则真不太好理解题目的意思,至少对我来说。

My first solution(21ms)

public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        sum = 0;
        DFS(root);
        return root;
    }

    int sum;
    private void DFS(TreeNode root){

        if(root == null) return;


        DFS(root.right);

        root.val = sum + root.val;
        sum = root.val;

        DFS(root.left);

    }

现在再来看看题目的意思,也就清楚了,它说的是让当前的节点加上之前遍历过的【节点和】得到的一个新值,oh,my god!我太蠢了。

所以说,只要明确递归的顺序就好了,访问从右节点开始,然后根节点,最后左节点,而在访问时,需要维护一个不断更新的sum值即可。当然,以上是从一棵树的角度来解决该问题的,但如果我们并没有【先序,中序,后序】的前期知识储备,那么该问题能否从一个最简单的递归形式来求解?答案是肯定的,树的遍历本质上就是递归,接下来咱们继这个例子,深入分析下该如何递归求解。

番外篇(递归本质)

首先,我们重新分析下题目,慢慢推得我们的解。它是一个BST,而BST是天然的递归结构,因为我们都知道,如果有根节点,那么根节点可以分为左子树和右子树,而左子树和右子树的形式和原始树是一模一样的。所以现在假设待求的方案为convertBST(root)

一个自然而然的想法就是,如果右子树的解决方案convertBST(root.right)和左子树的解决方案convertBST(root.left)能够合并成一个convertBST(root)的解决方案,那么该问题就完美解决了。

所以开始我们的方案探寻之旅吧,现在有了三个结构convertBST(root.right),root,convertBST(root.left),想方设法让它们组成一个更进一步的解。而一旦构建成功,那么它必然是正确的,它本质是建立在数学归纳法的公理体系中,因为在构建方案时,我们运用的就是数学归纳法,假设子问题成立,那么它更进一步的问题如果被子问题所表达,那么该命题成立。联想下数学归纳法,当前状态如P(n)为真,则它进一步的状态P(n++)能够由P(n)推得,那么对于所有n,P(n)均为真。是不是一模一样!请自行体会。

那为什么说它是一种递归呢?因为在最终解的形式上,它是把一个大问题,分解为了几个子问题,这也就是我们传统代码的表现形式,函数中调用了相同函数名,如上述例子所示。其实递归可以用数学公式所表达:

an++:=fn(an)

a_{n++} := f_n(a_n) 和代码是一模一样的,a为我们的方法名,而n++到n的变换是把一个大问题变成了一个小问题,fnf_n映射自然是我们努力需求的解决方案!

好了,回答这个问题上来吧,为了努力需求构建方案,我们需要明确子问题或者真正的大问题的性质,convertBST(root)有什么性质可以让我们利用?

就拿赛题中给出的例子来看,人为的去模拟它的构建过程,你会发现两点有趣的事情。

  • 性质1:构建过程,一定是先右节点,然后根节点,最后左节点。没有为什么, 由题目所决定。
  • 性质2:构建中有一变量,【sum of all keys】是不断变化的,它的累加顺序和遍历顺序相关,和当前节点的节点值相关。

所以,我们在构建代码时,只需要符合上述两种性质即可。代码结构可以如下所示:

solution(root){
    # 遍历右子树
    solution(root.right);
    # 遍历根节点
    root 操作
    # 遍历左子树
    solution(root.left);
}

简单分析下,假设我们的每个子问题满足性质1,那么显然由该代码结构,能推得root也符合性质1。这里需要强调一点的是,该递归结构的解是强烈依赖与子问题的求解顺序的,并不能随意颠倒。而在上一题中,对于子问题就没有该性质,因为大问题的性质并没有包含顺序关系,而此处则不一样。

关于性质2,那只需要有个全局变量,去不断记录更新它就完事了,即我们最终的代码:

public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        sum = 0;
        DFS(root);
        return root;
    }

    int sum;
    private void DFS(TreeNode root){

        if(root == null) return;

        DFS(root.right); 

        root.val = sum + root.val; //root 被 sum(右子树的sum值) 和当前值所更新
        sum = root.val; //sum 被更新       
        DFS(root.left); 

    }

逐一说明下,sum是如何被更新的。首先就是右子树了,代码进入到DFS(root.right),右子树本来就假设成立,所以sum值已被更新,此更新由假设条件来,接着root必须要做更新,这也是为什么sum的更新需写在两个子问题中间的原因,更新规则如代码所示root.val = sum + root.val;sum = root.val;那么,左子树该怎么更新呢?

这点着实令人不解,左子树也是一个DFS(root.left)就解决了sum的更新问题,原因在于,既然是左子问题,那么作为整体,它的root.left 的right自然为null,所以进行一次递归之后,略过了DFS(root.right),进行当前节点的更新,即左子结点的更新。

当然,我们也可以从迭代的角度去实现它,它是递归的一个可视化过程,即我们能形象的感知它的解是如何一步步形成的,而不像递归那么抽象,有兴趣的可以自己实现下。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Minimum Distance Between BST Nodes

    用户1147447
  • 776. Split BST

    思路: 问题的关键在于进行切分后,树的结构不能改变。影响BST的结构在于输入顺序,所以切分前后,维持输入顺序即可。而BST的层序遍历刚好是最初的输入顺序。所...

    用户1147447
  • LWC 62:742. Closest Leaf in a Binary Tree

    LWC 62:742. Closest Leaf in a Binary Tree 传送门:742. Closest Leaf in a Binary Tree...

    用户1147447
  • LeetCode 250. 统计同值子树(递归)

    Michael阿明
  • 原 树莓派(raspberry)启用roo

    霡霂
  • CentOS系统SSH免密后依然需要输入密码(已解决)

    1、问题 通过ssh-keygen -t rsa和ssh-copy-id -i node1操作后,免密登录依然需要输入密码。 [root@node1 ~]# s...

    程裕强
  • linux centos中添加删除修改环境变量,设置java环境变量

    前言 安装完软件必要添加环境变量。指令很少,然而长时间不写就会不自信:我写的对吗?于是百度开始,于是发现又是各有千秋。好吧,好记星不如烂笔头。当然,最重要的是,...

    Ryan-Miao
  • 查看linux里的initrd.img里的内容

    用户3765803
  • 手写AVL 树

    ShenduCC
  • Flat风格的Qml组合框

    Qt君

扫码关注云+社区

领取腾讯云代金券