[LeetCode] Binary Tree Paths

Problem:

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:
["1->2->5", "1->3"]

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<String>();
        if (root == null) {
            return result;
        }
        
        List<Integer> path = new ArrayList<Integer>();
        helper(root, path, result);
        return result;
    }
    
    private void helper(TreeNode root, List<Integer> path, List<String> result) {
        path.add(root.val);
        if (root.left != null) {
            helper(root.left, path, result);
        }
        if (root.right != null) {
            helper(root.right, path, result);
        } 
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                sb.append(path.get(i));
                if (i != path.size() - 1) {
                    sb.append("->");
                }
            }
            result.add(new String(sb));
        }
        path.remove(path.size() - 1);
    }
}

这个递归解法感觉有些复杂了，有没有更简单的解法呢？

[吐槽][口袋宝石] Room isConnected

package is.room.connected;

//How to calculate the time complexity of an algorithm using queue (or other data structure)?

//The time complexity of BFS is greater than DFS. Because the positions are enqueued multiple times?
//If use DFS the enqueued positions will never be enqueued again.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        List<Room> rooms = new ArrayList<Room>();
        rooms.add(new Room(0,0,5,5));
        rooms.add(new Room(5,4,1,1));
        System.out.println(isConnected(rooms, 9, 9));
    }
    
    public static boolean isConnected(List<Room> rooms, int m, int n) {
        if (rooms == null || rooms.size() == 0) {
            return false;
        }
        boolean[][] board = new boolean[m][n];
        
        //Calaulate the area of all the rooms
        int area = 0;
        for (Room r : rooms) {
            area += r.h * r.w;
            for (int i = r.x; i < r.x + r.w && i < m; i++) {
                for (int j = r.y; j < r.y + r.h && j < n; j++) {
                    board[i][j] = true;
                }
            }
        }
        
        //Use BFS to traverse start from the first room, take down the area of it
        Queue<Coordinate> queue = new LinkedList<Coordinate>();
        queue.offer(new Coordinate(rooms.get(0).x, rooms.get(0).y));
        
        int bfs_area = 0;
        while (!queue.isEmpty()) {
            Coordinate tmp = queue.poll();
            bfs_area += board[tmp.x][tmp.y] ? 1 : 0;
            board[tmp.x][tmp.y] = false;
            
            if (tmp.x + 1 < m && board[tmp.x + 1][tmp.y]) {
                queue.offer(new Coordinate(tmp.x + 1, tmp.y));
            }
            if (tmp.x - 1 >= 0 && board[tmp.x - 1][tmp.y]) {
                queue.offer(new Coordinate(tmp.x - 1, tmp.y));
            }
            if (tmp.y + 1 < n && board[tmp.x][tmp.y + 1]) {
                queue.offer(new Coordinate(tmp.x, tmp.y + 1));
            }
            if (tmp.y - 1 >= 0 && board[tmp.x][tmp.y - 1]) {
                queue.offer(new Coordinate(tmp.x, tmp.y - 1));
            }
        }

        return area == bfs_area;
    }
}

package is.room.connected;

public class Room {
    int x, y, w, h;
    
    //Assume (x, y) is the left bottom of the room
    //h is the height of the room
    //w is the width of the room
    
    public Room(int x, int y, int w, int h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
    }
}

package is.room.connected;

public class Coordinate {
    int x;
    int y;
    
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

[吐槽][口袋宝石] Top View of Binary Tree

//reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
//Question: Is it possible to solve this problem using BFS?
package binaryTree.top.view;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // TreeNode root = new TreeNode(1);//Used DFS first, caught a bug in
        // this test case, change to BFS
        // root.left = new TreeNode(2);
        // root.right = new TreeNode(3);
        // root.left.right = new TreeNode(4);
        // root.left.right.right = new TreeNode(5);
        // root.left.right.right.right = new TreeNode(6);

        topView(root);
    }

    public static void topView(TreeNode root) {
        if (root == null) {
            return;
        }

        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        Set<Integer> set = new HashSet<Integer>();
        Queue<QueueItem> queue = new LinkedList<QueueItem>();

        queue.offer(new QueueItem(root, 0));

        while (!queue.isEmpty()) {
            QueueItem item = queue.poll();
            if (item.node == null) {
                continue;
            }

            if (!set.contains(item.order)) {
                set.add(item.order);
                if (item.order <= 0) {
                    deque.addFirst(item.node);
                } else {
                    deque.addLast(item.node);
                }
            }

            queue.offer(new QueueItem(item.node.left, item.order - 1));
            queue.offer(new QueueItem(item.node.right, item.order + 1));
        }

        for (TreeNode t : deque) {
            System.out.print(t.value);
            System.out.print(" ");
        }
    }
}

package binaryTree.top.view;

public class QueueItem {
    TreeNode node;
    int order;
    public QueueItem(TreeNode node, int order) {
        this.node = node;
        this.order = order;
    }
}

package binaryTree.top.view;

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int value) {
        this.value = value;
    }
}

[吐槽][口袋宝石] Serialize/Deserialize a Binary Tree

import java.util.ArrayList;
import java.util.List;


public class SerializeSolution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        
        System.out.println(serialize(root));
        System.out.println(deserialize("0 1 3 # # 4 # # 2 5 # # 6 # #"));
    }
    
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        return Integer.toString(root.val) + " " + 
                serialize(root.left) + " " + serialize(root.right);
    }
    
    public static TreeNode deserialize(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        List<String> nodes = new ArrayList<String>();
        for (String tmp : s.split(" ")) {
            nodes.add(tmp);
        }
        return helper(nodes);    
    }
    
    public static TreeNode helper(List<String> nodes) {
        if (nodes.size() == 0) {
            return null;
        }
        
        if (nodes.get(0).equals("#")) {
            nodes.remove(0);
            return null;
        }
        
        int val = Integer.parseInt(nodes.get(0));
        nodes.remove(0);
        TreeNode root = new TreeNode(val);
        root.left = helper(nodes);
        root.right = helper(nodes);
        
        return root;
    }
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "TreeNode [val=" + val + ", left=" + left + ", right=" + right
                + "]";
    }
}

[吐槽] Snake Sequence

Problem:

You are given a grid of numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or the number below it is +1 or -1 its value. For example, 

1 3 2 6 8 

-9 7 1 -1 2 

1 5 0 1 9 

In this grid, (3, 2, 1, 0, 1) is a snake sequence. 

Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the maximum length).

Thinking:

Use dynamic programming to find the possible maximum of snake sequence in the matrix. Then, use another method to get that snake sequence.

Java Code:

import java.util.ArrayList;
import java.util.List;

public class Snake {
    public static void findSnake(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
        int max = findMax(matrix, dp);

        List<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (dp[i][j] == max) {
                    backtrack(matrix, dp, i, j, result, new ArrayList<String>());
                }
            }
        }

        for (List<String> list : result) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println();
        }
    }

    public static int findMax(int[][] matrix, int[][] dp) {
        int max = 1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i][j] = 1;
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i > 0 && Math.abs(matrix[i - 1][j] - matrix[i][j]) == 1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
                }
                if (j > 0 && Math.abs(matrix[i][j - 1] - matrix[i][j]) == 1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    public static void backtrack(int[][] matrix, int[][] dp, int i, int j,
            List<ArrayList<String>> result, List<String> path) {
        if (dp[i][j] == 1) {
            path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
            result.add(new ArrayList<String>(path));
            return;
        }

        if (i > 0 && dp[i - 1][j] == dp[i][j] - 1
                && Math.abs(matrix[i - 1][j] - matrix[i][j]) == 1) {
            path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
            backtrack(matrix, dp, i - 1, j, result, path);
            path.remove(path.size() - 1);
        }

        if (j > 0 && dp[i][j - 1] == dp[i][j] - 1
                && Math.abs(matrix[i][j - 1] - matrix[i][j]) == 1) {
            path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
            backtrack(matrix, dp, i, j - 1, result, path);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 5, 3, 2, 4 }, { 4, 3, 1, -1 }, { 2, 1, 0, -1 },
                { 6, 0, 7, 0 } };
        findSnake(matrix);
    }
}

Reference:
http://www.1point3acres.com/bbs/thread-111959-1-1.html
http://www.careercup.com/question?id=14946605