(LeetCode 动态规划（基础版） )337. 打家劫舍 III （深度优先搜索dfs）

思路：深度优先搜索dfs，时间复杂度0(n)。

每个节点，都有选和不选的权利，但选的话，当前子树的左右节点都不能选。细节看注释

C++版本：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://以root为根的子树，选or不选pair<int,int> dfs(TreeNode * root){if(root==nullptr) return {0,0};pair<int,int> left=dfs(root->left);pair<int,int> right=dfs(root->right);// 选int t1=root->val+left.second+right.second;// 不选int t2=max(left.first,left.second)+max(right.first,right.second);return {t1,t2};}int rob(TreeNode* root) {pair<int,int> p=dfs(root);return max(p.first,p.second);}
};

JAVA版本：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int[] dfs(TreeNode root){if(root==null){return new int[]{0,0};}int[] left=dfs(root.left);int[] right=dfs(root.right);//选int t1=left[1]+right[1]+root.val;// 不选int t2=Math.max(left[0],left[1])+Math.max(right[0],right[1]);return new int[]{t1,t2};}public int rob(TreeNode root) {int[] ans=dfs(root);return Math.max(ans[0],ans[1]);}
}

Go版本：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func rob(root *TreeNode) int {t1,t2:=dfs(root)return max(t1,t2)
}
func dfs(root *TreeNode) (int,int) {if root == nil {return 0,0}left_ok,left_no := dfs(root.Left)right_ok,right_no := dfs(root.Right)// 选t1:=root.Val + left_no + right_no// 不选t2:= max(left_ok,left_no)+max(right_ok,right_no)return t1,t2
}