[LeetCode] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means?

解题思路：
DSF,  先把所有的左结点存放到stack, pop的时候，print 当前位置的值，然后再遍历右子树

Java Code:

 public List inorderTraversal(TreeNode root) {
          Stack tmp = new Stack();
          List res = new ArrayList();
          
          TreeNode p = root;
          
          while( !tmp.isEmpty() || p != null ){
              while(p != null){
                  tmp.add(p);
                  p = p.left;
              }
           
               p = tmp.pop();
               res.add(p.val);
               p = p.right;
           
          }
          
        return res;
    }

[LeetCode] Binary Tree Level Order traversal II

Question:

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

Java Code:

public List> levelOrderBottom(TreeNode root) {
        List> res = new ArrayList>();
        Queue tmp = new LinkedList();
        Stack> res0 = new Stack>();
        
        if(root == null) return res;
        
        tmp.add(root);
        
        while(!tmp.isEmpty()){
            int size = tmp.size();
            List level = new ArrayList();
            
            for(int i = 0; i < size; i++){
                TreeNode node = tmp.poll();
                level.add(node.val);
                
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            
            res0.add(level);
        }
        
        while(!res0.isEmpty()){
            res.add(res0.pop());
        }
        
        return res;
    }

[LeetCode] Binary Tree Level order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? 

解题思路： BSF，一层一层的打印

Java Code

public List> levelOrder(TreeNode root) {
        List> res = new ArrayList>();
        Queue tmp = new LinkedList();
        
        if(root == null) return res;
        
        tmp.add(root);
        while(!tmp.isEmpty()){
            int size = tmp.size();
            List level = new ArrayList();
            
            for(int i = 0; i < size; i++){
                TreeNode node = tmp.poll();
                level.add(node.val);
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            
            res.add(level);
        }
        
        return res;
    }

[LeetCode] Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 解题思路：
用两个指针，一个指针遍历整个list，一个指针来指向当前小于x的最后一个node
这样每次找到一个新的node小于x，则把此node移到当前最后一个小于x的后面.
考虑到初始没有小于x的node,则增加一个dummy node 在开头，作为最开始的最后一个小于x的node

Java Code:

public ListNode partition(ListNode head, int x) {
        ListNode safeHead = new ListNode(0);
        safeHead.next = head;
        ListNode prev = safeHead;
        ListNode p = prev;
        
        while(p.next != null && p.next.val < x){
                p = p.next;
                prev = p;
        }
        
        while(p.next != null){
            if(p.next.val < x){          
                ListNode tmp = p.next;
                p.next = p.next.next;
                tmp.next = prev.next;
                prev.next = tmp;
                prev = prev.next;
                
              }else{
                p = p.next;
             }
        }
        
        return safeHead.next;
    }

[LeetCode] Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

解题思路：
DP解法，可以用recursion. 每次从一个state 转换到另外一个state的时候，我们需要知道，当前的位置(x, y), 以及匹配word的位置 pos, 还有就是为了避免重复visit一个元素，我们得有一个visited数组来记录走过的路径。 



Java Code:

public boolean exist(char[][] board, String word) {
         int row = board.length;
         int col = board[0].length;
          
         boolean[] visited = new boolean[row*col];
         
         for(int i = 0; i < row; i++){
             for(int j = 0; j < col; j++){
                 if(board[i][j] == word.charAt(0) && search(board, i, j, visited, word, 0)){
                     return true;
                 }
             }
         }
        return false;
    }
    
    public boolean search(char[][] board, int x, int y, boolean[] visited, String word, int pos){    
          if(pos == word.length() - 1){
              return true;
          }
       
          int row = board.length;
          int col = board[0].length;
          
          if(x > 0 && !visited[(x-1)*col + y] && word.charAt(pos+1) == board[x-1][y]){
              visited[x*col+y] = true;
              
              if(search(board, x-1, y, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
          }
          
           if(x+1 < row  && !visited[(x+1)*col + y] && word.charAt(pos+1) == board[x+1][y]){
              visited[x*col+y] = true;
              
              if(search(board, x+1, y, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
           }
           
           if(y > 0  && !visited[x*col + y - 1] && word.charAt(pos+1) == board[x][y-1]){
              visited[x*col+y] = true;
              
              if(search(board, x, y-1, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
           }
           
           if(y+1 < col  && !visited[x*col + y + 1] && word.charAt(pos+1) == board[x][y+1]){
              visited[x*col+y] = true;
              
              if(search(board, x, y+1, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
           }
          
        return false;
    }

[LeetCode] N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
] 

解题思路：

1.与N-Queens 2的思路一致，不过此题需要额外多的变量来记录所有的解。 

Java Code:

 public List solveNQueens(int n) {
        List res = new ArrayList();
        int[] solution = new int[n];
    
        String[] curr = new String[n];
        Nqueen1(1, solution, curr, res);
        return res;
    }
    
    public void Nqueen1(int level, int[] solution, String[] curr, List res){
        
        if(level == solution.length + 1){
            res.add(Arrays.copyOf(curr, level-1));
            return;
        }
        
        for(int i = 1; i <= solution.length; i++){
            int slop0 = Math.abs(i - level);
            
                int j = 0; 
                while(j < level && solution[j] != i && Math.abs(j + 1- level) != Math.abs(solution[j] - i)){
                    j++;
                }
                
                if(j == level){
                    String tmp = "";
                    
                    for(int t = 1; t <= solution.length; t++){
                        if(t==i) tmp += "Q";
                        else tmp += ".";
                    }
                    
                   
                    solution[level-1] = i;
                    curr[level-1] = tmp;
                    Nqueen1(level + 1, solution, curr, res);
                    solution[level - 1] = 0;
                    curr[level - 1] = ""; 
                }
         }
    }

[LeetCode] N-Queens

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.





解题思路：问题，每步的solution都与前面的solution相关。要满足，当前的位置i没有被前面使用过并且 |x-y| != |x0 -y0|

Java Code:

 public int totalNQueens(int n) {
          
         ArrayList solution = new ArrayList ();
           
         return totalNq(solution, 0, n);     
    }
    
    public int totalNq(ArrayList orders, int level, int n){
           int total = 0;
           
           if(level == n) {
               return 1;
           }else{
               for(int col = 0; col < n; col++){  
                   
                   if(!orders.contains(col)){
                       int j = 0;
                       while(j < level && Math.abs(j - level) != Math.abs(orders.get(j) - col) ){              
                           j++;
                       }
                       
                       if( j == level){
                           orders.add(level, col);
                           total +=totalNq(orders, level + 1,n); 
                           orders.remove(level);
                       }
                   }
               }
           } 
           
           return total;
    }