leetcode 8.17-8.23

2020-08-21

111 二叉树的最小深度
337 打家劫舍III

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以用深度优先搜索和广度优先搜索。

深度优先搜索：整棵树的的最小深度=$min(min_depth(left), min_depth(right))$，可以用递归计算。

广度优先搜索：比较好的一点是，最先碰到的叶子节点的深度就是最小深度。以下代码为广度优先搜索。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        if (root->left==NULL && root->right==NULL)
            return 1;
        
        std::queue<TreeNode*> q;
        int depth = 1;
        q.push(root);
        while(!q.empty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                auto p = q.front();
                q.pop();
                if (p->left==NULL && p->right==NULL)
                    return depth;
                if(p->left)  q.push(p->left);
                if(p->right) q.push(p->right);
            }
            depth++;
        }
        return depth;
    }
};

337. 打家劫舍III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：递归+动态规划，$ret = max(left+right, left.left+left.right+right.left+right.right+root)$

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return root.val
        ret1 = self.rob(root.left) + self.rob(root.right)
        ret2 = 0
        if root.left != None and root.right != None:
            ret2 = self.rob(root.left.left) + self.rob(root.left.right) + self.rob(root.right.left) + self.rob(root.right.right)
        elif root.left != None:
            ret2 = self.rob(root.left.left) + self.rob(root.left.right)
        else:
            ret2 = self.rob(root.right.left) + self.rob(root.right.right)
        return max(ret1, ret2+root.val)

上述代码超时。

参考题解，思路差不多，但是表述比上述公式简洁一些，s表示选择当前节点，n表示不选择当前节点

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def _rob(root):
            if not root: return 0, 0
            
            ls, ln = _rob(root.left)
            rs, rn = _rob(root.right)
            
            return root.val + ln + rn, max(ls, ln) + max(rs, rn)

        return max(_rob(root))