7.7号刷题

发表于 | 分类于 | 0 comments

第一题 156. Binary Tree Upside Down

题目描述

将一棵树按照特定要求进行倒转

算法

详见链接

Recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
public class upsideDownBinaryTree156 {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null)
            return root;
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
        return newRoot;
    }
}
iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre = null;
        TreeNode curRight = null;
        TreeNode next = null;
        while (cur != null) {
            next = cur.left;
            cur.left = curRight;
            curRight = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;        
    }
}

第二题543. Diameter of Binary Tree

题目描述

给定一棵二叉树，计算任意两节点之间的边数的最大值。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class diameterOfBinaryTree543 {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        helper(root);
        return max;
    }
    public int helper(TreeNode root) {
        if (root == null) return - 1;
        int leftLegth = helper(root.left) + 1;
        int rightLegth = helper(root.right) + 1;
        max = Math.max(max, leftLegth + rightLegth);
        return Math.max(leftLegth, rightLegth);
    }
}

第三题337. House Robber III

题目描述

小偷又给自己找了一个新的偷盗场所。这片区域只有一个入口，叫做“根”。除了根以外，每一个房间有且仅有一个父级房间。在踩点之后，聪明的盗贼发现“所有的房间形成了一棵二叉树”。如果两个有边直接相连的房间在同一晚上都失窃，就会自动联络警察。

判断盗贼在不惊动警察的情况下最多可以偷到的金钱数目。

测试用例如题目描述。

算法

Map 存储访问过的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class rob337 {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> map = new HashMap<>();
        return helper(root, map);
    }
    public int helper(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) return 0;
        if (map.containsKey(root)) return map.get(root);
        int val = 0;
        //Rob the current node
        if (root.left != null) {
            val += helper(root.left.left, map) + helper(root.left.right, map);
        }
        if (root.right != null) {
            val += helper(root.right.left, map) + helper(root.right.right, map);
        }
        int max = Math.max(root.val + val, helper(root.left, map) + helper(root.right, map));
        map.put(root, max);
        return max;
    }
}

用数组返回当前状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int rob(TreeNode root) {
        int[] res = backtrack(root);
        return Math.max(res[0], res[1]);
    }
    public int[] backtrack(TreeNode root) {
        if (root == null) return new int[2];
        
        int[] left = backtrack(root.left);
        int[] right = backtrack(root.right);
        int[] res = new int[2];
        
        //Does not rob the current
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //Rob current node
        res[1] = left[0] + right[0] + root.val;
        return res;
    }
}