FilesExpand file tree

 master

/

HouseRobberIII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (42 loc) · 1.31 KB

 master

/

HouseRobberIII.java

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (42 loc) · 1.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

public class HouseRobberIII {

/**

* 效率堪忧，耗时1000ms

*/

public int rob(TreeNode root) {

return rob(root, true);

}

/**

* @param rob true表示不定，false表示不选root

*/

private int rob(TreeNode root, boolean rob) {

if (root == null) {

return 0;

}

if (rob) {

return Math.max(root.val + rob(root.left, false) + rob(root.right, false),

rob(root.left, true) + rob(root.right, true));

} else {

return rob(root.left, true) + rob(root.right, true);

}

}

/**

* 优化写法如下，耗时1ms

* 这里将两种情况都保存下来并返回给上层，避免了多次重复计算

* val[0]表示不rob当前节点，val[1]表示rob当前节点

*/

public int rob2(TreeNode root) {

int[] val = helper(root);

return Math.max(val[0], val[1]);

}

private int[] helper(TreeNode node) {

if (node == null) {

return new int[]{0,0};

}

int[] left = helper(node.left);

int[] right = helper(node.right);

int[] value = new int[2];

value[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

value[1] = node.val + left[0] + right[0];

return value;

}

}