[LeetCode]树的问题（一）：102层序遍历-337打家劫舍III

DFS和BFS遍历

  1. 递归的DFS遍历

    1
    2
    3
    4
    5
    void dfs (Node root) {
    	if (root == null) return;
    	dfs(root.left);
    	dfs(root.right);
    }

  2. 使用队列的BFS遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void bfs (Node root) {
    	Queue<Node> queue = new LinkedList<>();
    	queue.add(root);

    	while(!queue.isEmpty()) {
    		Node node = queue.poll();
    		if (node.left != null) queue.add(node.left);
    		if (node.right != null) queue.add(node.right);
    	}
    }

BFS的应用 - No.102 二叉树的层序遍历 Binary Tree Level Order Traversal

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
// given a binary tree
//		3
//   / \
//  9  20
//    /  \
//   15   7
// return a List<List<Integer>> like:
//
//[
//  [3],
//  [9,20],
//  [15,7]
//]
public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) return res;
        queue.add(root);
        int levelCount;
        List<Integer> singleLevel = new LinkedList<>();
        while(!queue.isEmpty()) {
            levelCount = queue.size();
            for (int i = 0; i < levelCount; i++) {
                TreeNode current = queue.poll();
                if (current.left != null) queue.add(current.left);
                if (current.right != null) queue.add(current.right);
                singleLevel.add(current.val);
            }
            res.add(singleLevel);
            singleLevel = new LinkedList<>();
        }
        return res;
    }

DFS（递归思路）的应用 - No.337 打家劫舍 III House Robber III

一开始的思路是，先层序遍历得到一个数组 levelSum[] 存储每层的节点的和，用常规的dp做。看评论发现如 [2, 1, 3, null, 4] 这样一棵树，对于相邻的两层结点，第一层右边的结点和第二层左边的结点可以求和，这棵树的最大值为7，而非层序遍历得到的6。所以应该自下向上的（递归）求解，每个结点计算在当前结点作为根的情况下，能偷到的最大值。

  1. 暴力递归法 - 每个点返回【当前点作为根可以偷到的最大值】，which means 当前点可能偷，也可能不偷。

    1
    2
    3
    4
    5
    6
    // method1: 当前点加四个孙子可以偷到的最大值之和
    int method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right);
    // method2: 两个儿子可以偷到的最大值之和
    int method2 = rob(root.left) + rob(root.right);

    return Math.max(method1, method2);

    这种解法速度太慢，因为【重复计算】，爷爷层在method1中计算了孙子层的和，父亲层又在method2中计算了一遍孙子层的和。

  2. 优化的递归解法①（记忆化递归） - 定义一个HashMap保存计算过的值，若当前计算的结点已包含在这个hashmap中，直接返回hashmap.get(currentNode)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int rob(TreeNode root) {
            if (root == null) return 0;
            if (hashmap.containsKey(root)) return hashmap.get(root);
            int rob_current = root.val;
            if (root.left != null) rob_current += rob(root.left.left) + rob(root.left.right);
            if (root.right != null) rob_current += rob(root.right.left) + rob(root.right.right);
            int no_rob_current = rob(root.left) + rob(root.right);
            int current_max = Math.max(rob_current, no_rob_current);
            hashmap.put(root, current_max);
            return current_max;
        }
    // 用时 3ms, 内存 39.3 MB

  3. 进一步优化的递归解法② - 前两种方法重复性计算的根本原因在于，需要不断接触当前结点的儿子节点和孙子节点，相当于一次只迈一级台阶，但脚要多碰一次下面的下面一级。如果，儿子结点能提供孙子结点相关的信息，就可以不必再多沾地一次。参考自力扣题解区：方法不再返回一个int值，反而返回一个int[]数组，int[0]代表该结点没被抢的最大值，int[1]代表该节点被抢了的最大值。而前两种思路中，访问孙子结点的部分，就可以转变为左右两节点的int[0]相加。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int rob(TreeNode root) {
            int[] root_res = robHelper(root);
            return Math.max(root_res[0], root_res[1]);
        }
        private int[] robHelper(TreeNode root) {
            if (root == null) return new int[]{0, 0};
            int[] left = robHelper(root.left);
            int[] right = robHelper(root.right);

            int rob_current = left[0] + right[0] + root.val;
            int no_rob_current = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            return new int[]{no_rob_current, rob_current};
        }
    // 用时 1ms, 内存 39.2 MB