题目地址：

https://leetcode.com/problems/house-robber-iii/

给定一个二叉树，要求在其中选取若干数使得和最大，但相邻的两个节点的数不能同时选。

思路是动态规划。设$x$表示树根，$l$表示左子树，$r$表示右子树，$f[x][0]$表示当不选$x$的时候，从$x$为树根的这棵树上能选数的最大和；$f[x][1]$表示当选$x$的时候，从$x$为树根的这棵树上能选数的最大和。则：$$\begin{gathered} f[x][0]=\max \{f[l][0],f[l][1]\}+\max \{f[r][0],f[r][1]\} \\ f[x][1]=x+f[l][0]+f[r][0] \end{gathered}$$答案就是$\max \{f[x][0],f[x][1]\}$。一遍DFS即可。代码如下：

public class Solution { public int rob(TreeNode root) { if (root == null) { return 0; } int[] dp = dfs(root); return Math.max(dp[0], dp[1]); } private int[] dfs(TreeNode root) { if (root == null) { return new int[]{0, 0}; } int[] dp = new int[2]; int[] left = dfs(root.left), right = dfs(root.right); dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); dp[1] = root.val + left[0] + right[0]; return dp; } } class TreeNode { int val; TreeNode left, right; public TreeNode(int val) { this.val = val; } }

时间复杂度$O(n)$，空间$O(h)$。