美文网首页
2018-11-19LeetCode 339 打家劫舍3

2018-11-19LeetCode 339 打家劫舍3

作者: 北子萌 | 来源:发表于2018-11-19 15:49 被阅读0次

    递归法解决:

    分别讨论是否包含还是不包含root的情况,然后通过回溯法解决。

    具体代码如下:

    /**

    * Definition for a binary tree node.

    * public class TreeNode {

    *    int val;

    *    TreeNode left;

    *    TreeNode right;

    *    TreeNode(int x) { val = x; }

    * }

    */

    class Solution {

        public int rob(TreeNode root) {

            if(root==null)

            {

                return 0;

            }

            return Math.max(robInclude(root),robExclude(root));

        }

        public int robExclude(TreeNode root)

        {

            if(root==null)

            {

                return 0;

            }

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

        }

        public int robInclude(TreeNode root)

        {

            if(root==null)

            {

                return 0;

            }

            return root.val+robExclude(root.left)+robExclude(root.right);

        }

    }

    相关文章

      网友评论

          本文标题:2018-11-19LeetCode 339 打家劫舍3

          本文链接:https://www.haomeiwen.com/subject/ftfafqtx.html