337. House Robber III

概述一、题目 　　1、审题　 　　 　　2、分析 　　　　给出一棵二叉树，取二叉树中的节点值，其中不能获取相邻层的二叉树节点。   二、解答 　　1、思路 　　　　方法一、 　　　　　　分两种情况， 情况一： root.val + root.left.left.val + root.left.right.val + root.right.left.val + root.right.right.val 

一、题目

　　1、审题　

　　

　　2、分析

　　　　给出一棵二叉树，取二叉树中的节点值，其中不能获取相邻层的二叉树节点。

 

二、解答

　　1、思路

　　　　方法一、

　　　　　　分两种情况， 情况一： root.val + root.left.left.val + root.left.right.val + root.right.left.val + root.right.right.val 

　　　　　　情况二： root.left.val + root.right.val

　　　　　　然后取这两种情况的最大值，进行递归！

 

    public int rob(TreeNode root) {        if(root == null)    		return 0;    	    	int val = 0;    	if(root.left != null)     		val += rob(root.left.left) + rob(root.left.right);    	    	if(root.right != null)    		val += rob(root.right.left) + rob(root.right.right);    	    	return Math.max(val + root.val,rob(root.left) + rob(root.right));    }

　　

　　方法二、

　　　　由于方法一中，每一次递归有很多重复的计算。采用 Map <Node， val> 记录当前节点对应的最大值！减少递归的重复计算！

    public int rob(TreeNode root) {        return robSub(root,new HashMap<TreeNode,Integer>());	}	    private int robSub(TreeNode root,HashMap<TreeNode,Integer> map) {    	if(root == null)    		return 0;    	if(map.containsKey(root))    		return map.get(root);    	    	int val = 0;    	if(root.left != null)    		val += robSub(root.left.left,map) + robSub(root.left.right,map);    	    	if(root.right != null)    		val += robSub(root.right.left,map) + robSub(root.right.right,map);    	    	val = Math.max(val + root.val,robSub(root.left,map) + robSub(root.right,map));    	map.put(root,val);    	return val;	}

总结

以上是内存溢出为你收集整理的337. House Robber III全部内容，希望文章能够帮你解决337. House Robber III所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。