算法 Leetcode 姐姐

今天, 小姐姐推荐了一个有关树的问题House Robber III.

题目大意

需要得到二叉树从根到叶子的最大路径之和, 但是相连的两个点无法同时取到.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:
     3
    / \
   2   3
    \   \
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

解法一

我看过题目后自己想了一种方法:

因为一个点取到后, 他的子节点是不能计算的. 所以对当前根节点来说, 有两种情况, “可以取” 或是 “不可以取”,

  • 对于 根节点不可以取的情况: 返回其左右子树的最大值
  • 对于 根节点可以取的情况: 返回 “取当前点”, 和 “不取当前点”两种情况下的最大值

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int robMax(TreeNode* r, bool couldUse) {
    if(r == nullptr) return 0;

    if(!couldUse) { // 当前根节点无法使用
        int left = robMax(r->left, true);
        int right = robMax(r->right, true);
        return left + right;
    }

    // 1. 取当前值, 左右节点均不可取
    // 2. 不取当前值, 左右节点均为可取状态
    return max( r->val + robMax(r->left, false) + robMax(r->right, false),
                robMax(r->left, true) + robMax(r->right, true));
}

int rob(TreeNode* root) {
    if(root == nullptr) return 0;

    return robMax(root, true);
}

运行结果

运行结果实在悲惨

slow

解法二

由于单个函数的返回值信息太少了, 以至于我们需要对每个节点讨论可取与不可取的情况

如果我们的函数能多返回一点信息, 将左子树, 右子树的情况也返回, 这样考虑,

函数中 返回 “根节点的值与左右子树的所有子树之和” 与 “左右子树最大值之和”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int robFast(TreeNode* r, int& lMax, int &rMax) {
    if(r == nullptr) return 0;
    int ll = 0;
    int lr = 0;
    int rl = 0;
    int rr = 0;

    lMax = robFast(r->left, ll, lr);
    rMax = robFast(r->right, rl, rr);

    return max(r->val+ ll + lr + rl + rr, lMax + rMax);
}

int rob(TreeNode* root) {
    if(root == nullptr) return 0;

    int l = 0, r = 0;
    return robFast(root, l, r);
}

运行结果

fast

运行时的一些分析

以下图所示的树为例:

1
2
3
4
5
    3
   / \
  4   5
 / \   \ 
1   3   1
  • 方法一:

方法一

从图中可以看出, 从根节点到叶子节点, 每一层的时间复杂度是以一种斐波那契数列的方式进行增长的 (我承认自己的智商从图中看不出来的, 你可以使用一条形似单链表的树来进行分析, 会发现每一层的复杂度是以两个斐波那契数相加而成)

下面是一条形似单链表的树的运算方式

1
2
3
4
5
6
7
1            t                      1t + 0f
          /     \
2:     t            f               1t + 1f
     /  \           |
3   t    f          t               2t + 1f
   / \   |         / \
4 t   f  t        t   f             3t + 2f

斐波那契数列中: 前n项和等于第n+2项减1 证明在此：Sum of Sequence of Fibonacci Numbers

这应该是类似指数次数的递增, 所以, 产生那么大的运行时间, 的确如此.

  • 方法二:

方法二

反观解法二, 可以看出每个点经过了一次, 时间复杂度严格的等于O(n)

一些思考

在写递归函数时, 我们尽量将每个函数的效用榨干, 也就是说, 能进行返回的值, 全部返回回来. 也许利用这些返回值的能够有效的减少函数递归次数, 从而提高性能.

上面的解法二中, 将左右子树能取到的最大值也进行了返回, 函数性能得到了比较好的提升.