leetcode / Medium
4 分钟 读完 (大约 643 个字)

house-robber-iii

题目链接：house-robber-iii

题目描述

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

题目分析

不相邻的节点和最大值，让我们可以分成两种情况：

  1. 该节点值 + 他的间接子树最大值的和
  2. 他的直接子树最大值的和

算法

深度优先遍历（Depth-first-Search）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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) {
        return dfs(root);
    }
    
    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int result = root.val;
        if (root.left != null) result += dfs(root.left.left) + dfs(root.left.right);    // 该节点左间接子树和最大值
        if (root.right != null) result += dfs(root.right.left) + dfs(root.right.right); // 该节点右间接子树和最大值
        result = Math.max(result, dfs(root.left) + dfs(root.right));    // 比较选择包含该节点还是不包含该节点的和最大值
        return result;
    }
}

深度优先遍历（优化）（Depth-first-Search）

在上一解法中，明显可以发现，我们在寻找当前树的最大值时，还需要寻找子树的子树最大值，而在寻找子树的最大值时，我们已经查找过了子树的子树的最大值，即有很多计算是重复的。因此，在深搜过程中，同时返回包含该节点和最大值和不包含该节点和最大值可以给我们运行时间上带来不少优化。

代码

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
26
27
/**
 * 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) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
    
    // [0] => 包含该节点的和最大值
    // [1] => 不包含该节点的和最大值
    public int[] dfs(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        int result = root.val;
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        return new int[] {
            root.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])
            };
    }
}
leetcode / Medium
6 分钟 读完 (大约 948 个字)

all-nodes-distance-k-in-binary-tree

题目链接：all-nodes-distance-k-in-binary-tree

题目描述

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

题目分析

  1. 距离给定节点距离为K的节点有两种情况：第一种是他的子节点，这种情况比较容易通过遍历得到。第二种是他的祖先节点的其他子树，对于这种情况，我们需要能找到节点的祖先节点的方法。
  2. 找到某节点父节点的方法可有两种，一种是深搜回退到他的父节点，一种是建立子节点到父节点的映射。

算法

深度优先遍历（Depth-first-Search）

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> result;
    int k;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        result = new ArrayList<>();
        k = K;
        dfs(root, target);
        return result;
    }

    public int dfs(TreeNode cur, TreeNode target) {
        if (cur == null) {
            return -1;            // 返回-1表示在当前子树没有找到目标节点
        }
        if (cur == target) {
            subtreeAdd(cur, 0); // 找到目标节点了，对目标节点子树进行查找
            return 1; // 返回他的父节点到目标节点距离
        } else {
            int d = dfs(cur.left, target);
            if (d != -1) {
                // 目标节点在左子树
                if (d == k) {
                    // 当前节点符合到目标节点距离，添加到结果集
                    result.add(cur.val);                    
                }
                subtreeAdd(cur.right, d + 1);  // 寻找当前节点右子树符合条件的节点
                return d + 1; // 返回当前节点父节点到目标节点的距离
            } else {
                d = dfs(cur.right, target);
                if (d != -1) {
                    // 目标节点在右子树
                    if (d == k) {
                        // 当前节点符合到目标节点距离，添加到结果集
                        result.add(cur.val);    
                    }
                    subtreeAdd(cur.left, d + 1);    // 寻找当前节点左子树符合条件的节点
                    return d + 1;   // 返回当前节点父节点到目标节点的距离
                }
            }
            return -1;  // 目标节点在当前子树不存在
        }
    }

    // 查找当前子树符合到目标节点距离的值，保存结果
    public void subtreeAdd(TreeNode cur, int d) {
        if (cur == null || d > k) {
            return;
        }
        if (k == d) {
            result.add(cur.val);            
        }
        subtreeAdd(cur.left, d + 1);
        subtreeAdd(cur.right, d + 1);
    }
}

宽度优先搜索（Breadth-first-Search）

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, TreeNode> child2parent = new HashMap<>();
        dfs(root, null, child2parent);  // 建立子节点到父节点的映射

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(target);
        queue.offer(null);  // 以null为到目标节点距离相同的节点集分割点

        HashSet<TreeNode> seen = new HashSet<>();   // 标记查找过的节点，保证入队节点距离目标节点的距离是逐渐增加的
        seen.add(target);
        seen.add(null);

        List<Integer> result = new ArrayList<>();   // 保存结果
        while (!queue.isEmpty()) {
            TreeNode tmp;
            if (K == 0) {
                // 到目标节点距离为K，将当前队列中所有节点集保存到结果，null节点是分割点
                while ((tmp = queue.poll()) != null) {
                    result.add(tmp.val);
                }
            } else {
                while ((tmp = queue.poll()) != null) {
                    // 遍历当前距离目标节点距离相等的所有节点，分别将他的父节点、左子节点、右子节点
                    // 入队（如果这些节点没有被标记过，即他们离目标节点的距离都是+1）
                    if (!seen.contains(tmp.left)) {
                        seen.add(tmp.left);
                        queue.offer(tmp.left);
                    }
                    if (!seen.contains(tmp.right)) {
                        seen.add(tmp.right);
                        queue.offer(tmp.right);
                    }
                    if (!seen.contains(child2parent.get(tmp))) {
                        seen.add(child2parent.get(tmp));
                        queue.offer(child2parent.get(tmp));
                    }
                }
                queue.offer(null); // null入队分割下次循环
                K--; // 目标距离-1
            }
        }
        return result;
    }
    
    public void dfs(TreeNode cur, TreeNode parent, Map<TreeNode, TreeNode> child2parent) {
        if (cur != null) {
            child2parent.put(cur, parent);
            dfs(cur.left, cur, child2parent);
            dfs(cur.right, cur, child2parent);
        }
    }
}
在二叉树中分配硬币
leetcode / Medium
7 分钟 读完 (大约 998 个字)

在二叉树中分配硬币

题目链接：distribute-coins-in-binary-tree

题目描述

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。返回使每个结点上只有一枚硬币所需的移动次数。

题目分析

  1. 要使得硬币移动次数最少，我们应该把结点中多余的硬币移到离它最近且需要硬币的结点上。
  2. 由于是在二叉树上移动，则硬币移动轨迹一定是从某结点移动到他的父节点或者子节点上。
  3. 从需要硬币的结点到有多余硬币的结点的距离等于从有多余硬币结点的距离到需要硬币的结点的距离。
  4. 一个结点可能有两个子节点，因此，如果该结点需要硬币或者有多余的硬币，我们无法一下子确定该硬币应该从左子节点还是右子节点获得或者移向左子节点还是右子节点；而一个结点一定只有一个父节点，因此，如果该结点需要硬币或者有多余的硬币，移动轨迹一定会经过他的父节点。

算法分析

采用深度搜索优先的思路，从树的叶子节点出发，如果该结点（设为cur）需要硬币，则从他的父节点获得，如果该结点有多余的硬币，则多余的硬币全部移动向他的父节点。即该结点的初始值为cur.val,从该结点递归到他的父节点，移动次数增加Math.abs(cur.val - 1)。该结点cur.val变为期待的1，如果该结点的值cur.val > 1，则他的父节点的的值cur.parent.val = cur.parent.val + cur.val - 1;如果该结点的值cur.val <= 1,则他的父节点的的值cur.parent.val = cur.parent.val - (-cur.val + 1)。逐步递归，直到遍历完整棵树，则可得出结果。

代码

解法一

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
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int moves = 0;      // 记录移动次数
    
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return moves;
    }
    
    // 该方法返回值为移动完成后结点cur拥有多余的或者缺少的硬币数量，即cur.val - 1。
    public int dfs(TreeNode cur) {
        if (cur == null) return 0;
        int l = dfs(cur.left);
        int r = dfs(cur.right);
        moves += Math.abs(l) + Math.abs(r);         // 总结果加上左右子节点硬币流向父节点或从父节点移动过去需要的次数
        return cur.val + l + r - 1;         // 当前结点缺少的的或者多余的硬币数量
    }
    
}

解法二

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
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public int distributeCoins(TreeNode root) {
        return dfs(root, null);
    }
    
    // 该方法返回值为移动好当前结点（包括他的子节点，即当前结点表示的树）需要的移动次数
    public int dfs(TreeNode cur, TreeNode parent) {
        if (cur == null) return 0;
        int l = dfs(cur.left, cur);
        int r = dfs(cur.right, cur);
        
        int result = l + r;         // 移动好左右子树需要的移动次数
        // 修改当前结点父节点的硬币值
        if (cur.val < 1) {
            // 当前结点硬币值小于1，从父节点移动硬币到当前结点,父节点硬币数量减少
            result += (1 - cur.val);
            parent.val -= (1 - cur.val);
        } else if (cur.val > 1) {
            // 当前结点硬币值大于1，将多余的硬币值移动到父节点，父节点硬币数量增加
            result += (cur.val - 1);
            parent.val += (cur.val - 1);
        }
        return result;
    }
    
}
关注我

分类

标签云

Bit-Manipulation Breadth-first-Search Depth-first-Search Dynamic-Programming Graph Stack Tree Union-Find

最新文章

归档

标签

Bit-Manipulation 1
Breadth-first-Search 3
Depth-first-Search 14
Dynamic-Programming 1
Graph 3
Stack 1
Tree 3
Union-Find 3

最新文章

归档

标签

Bit-Manipulation 1
Breadth-first-Search 3
Depth-first-Search 14
Dynamic-Programming 1
Graph 3
Stack 1
Tree 3
Union-Find 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×