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

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434829

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)，进行当前节点的更新，即左子结点的更新。

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