【力扣-二叉树】23、把二叉搜索树转换成累加树（538） 5

发表于

「这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战」

538. 把二叉搜索树转换为累加树

题目描述

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

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

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

注意： 本题和 1038: leetcode-cn.com/problems/bi… 相同

示例 1：

1
2
csharp复制代码输入： [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：

1
2
ini复制代码输入： root = [0,null,1]
输出： [1,null,1]

示例 3：

1
2
ini复制代码输入： root = [1,0,2]
输出： [3,3,2]

示例 4：

1
2
ini复制代码输入： root = [3,2,4,1]
输出： [7,9,4,10]

提示：

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

解析

根据给出的示例可以发现，所谓的累加树，其实就是根据中序遍历的顺序，求出每个节点到最后一个节点值的累加和作为当前节点的值。

法1

  • 使用两次中序遍历：
    • 1、第一次遍历记录每个元素的值，并且求出最大值
    • 2、第二次遍历修改每个元素的值
      • 规律：当前元素的新值等于前驱节点的新值-前驱节点的旧值
      • 所以：使用三个指针来记录值的变化，
        • 其中preOld指针指向前驱节点的旧值
        • preNew指针指向前驱节点的新值
        • tmp 指针记录当前节点修改前的值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
c++复制代码class Solution
{
public:
    TreeNode *convertBST(TreeNode *root)
    {
        // 第一次遍历，求出所有节点值的累加和
        traversal(root);
        // 第二次遍历，更新节点的累加和
        changeVal(root);
        // 返回根节点
        return root;
    }

private:
    int sum;                            // 记录所有节点值的累加和
    TreeNode *preOld = new TreeNode(0); // 记录前驱节点的旧值
    TreeNode *preNew = NULL;            // 记录前驱节点的新值
    TreeNode *tmp = new TreeNode(0);    // 临时节点，记录当前节点的旧值

    // 第一次中序遍历，求节点值累加和
    void traversal(TreeNode *cur)
    {
        if (cur == NULL)
        {
            return;
        }
        // 左
        if (cur->left)
        {
            traversal(cur->left);
        }

        // 中
        sum += cur->val;

        // 右
        if (cur->right)
        {
            traversal(cur->right);
        }
    }

    // 第二次中序遍历，修改节点的值
    void changeVal(TreeNode *cur)
    {
        if (cur == NULL)
        {
            return;
        }

        // 左
        if (cur->left)
        {
            changeVal(cur->left);
        }

        // 中
        if (preNew == NULL)
        {
            // 当前驱节点指向空时，找到左子树的最左叶子节点
            preOld->val = cur->val; // 记录旧值
            cur->val = sum;         // 更新值
            preNew = cur;           // 更新前驱节点指针
        }
        else
        {
            tmp->val = cur->val;                  // 记录当前节点的旧值
            cur->val = preNew->val - preOld->val; // 更新当前节点的值
            preOld->val = tmp->val;               // 更新前驱节点旧值
            preNew = cur;                         // 更新前驱节点
        }

        // 右
        if (cur->right)
        {
            changeVal(cur->right);
        }
    }
};

法2

对二叉搜索树进行中序遍历可以得到一个有序数组,数组元素更新的规律可以看做是从后向前累加，所以可以使用逆向中序遍历，即遍历顺序为 右->中->左

  • 使用递归方法
    • 1、确定递归的参数与返回值
      • 参数：当前节点 cur 以及 前驱节点 pre
    • 2、确定递归的终止条件
      • 遇到空节点直接返回
    • 3、确定单层循环的逻辑
      • 先遍历右孩子，
      • 遍历根节点，同时修改节点元素的值
      • 最后左孩子

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
c++复制代码class Solution
{
public:
    TreeNode *convertBST(TreeNode *root)
    {
        traversal(root);
        return root;
    }

private:
    TreeNode *pre = new TreeNode(0); // 前驱节点值初始为0
    void traversal(TreeNode *cur)
    {
        if (cur == NULL)
        {
            return;
        }

        // 右
        if (cur->right)
        {
            traversal(cur->right);
        }

        
        // 当前节点的值等于前一个节点的值+当前节点的值
        cur->val = pre->val + cur->val;
        pre = cur;
        // 左
        if (cur->left)
        {
            traversal(cur->left);
        }
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%