[LeetCode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 

解题思路：

无向图的邻居，要注意避免重复建设node. 所以我们用一个hashmap来存储已经有的点。当遇到了已经有的点，直接从hahmap里取。

Java Code:

 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
       
        if(node == null){
            return null;
        }
        
        HashMap allnodes = new HashMap(); 
        List newnodes= new ArrayList();
        List oldnodes= new ArrayList();
       
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        allnodes.put(node.label, newNode);
        
        newnodes.add(newNode);
        oldnodes.add(node);
        
      do{  
          List newNext= new ArrayList();
          List oldNext= new ArrayList();
        
          for(int i = 0; i < oldnodes.size(); i++){
              UndirectedGraphNode oldnode = oldnodes.get(i);
            
            if(oldnode.neighbors == null){
                continue;
            }
            
            List oldneibors = oldnode.neighbors;
            List newneibors = new ArrayList();
            
            for(UndirectedGraphNode curr : oldneibors){
                UndirectedGraphNode newnode = null;
                if(allnodes.containsKey(curr.label)){
                   newnode = allnodes.get(curr.label);
                }else{
                  newnode = new UndirectedGraphNode(curr.label);
                  allnodes.put(curr.label, newnode);
                  newNext.add(newnode);
                  oldNext.add(curr);
                }
                newneibors.add(newnode);
            }                  
            newnodes.get(i).neighbors = newneibors;
        }
        
        oldnodes = oldNext;
        newnodes = newNext;
      }while(!oldnodes.isEmpty());
      
      return newNode;
    }

[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] Populating Next Right Pointer Each node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

        1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Java Code:

 public void connect(TreeLinkNode root) {
         if(root == null) return;
        
        Queue tmp = new LinkedList();
        tmp.add(root);
        
        while(!tmp.isEmpty()){
            int size = tmp.size();
            TreeLinkNode prev = null;
            
            for(int i = 0; i < size; i++){
                TreeLinkNode node = tmp.poll();
                
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
                
                if(i == 0){
                    prev = node;
                }else{
                    prev.next = node;
                    prev = prev.next;
                }
            }
        }
            
    }

[LeetCode] Maximum depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Java code:

 public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        
        int max = 0;
        Queue tmp = new LinkedList();
        tmp.add(root);
        
        while(!tmp.isEmpty()){
            max++;
            int size = tmp.size();
            for(int i = 0; i < size; i++){
                TreeNode node = tmp.poll();
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
        }
        
        return max;
    }

[LeetCode] Minimum depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解题思路：典型的BSF. 用一个Queue就好了

Java code:

public int minDepth(TreeNode root) {
        Queue tmp = new LinkedList ();      
        if(root == null) return 0;   
        
        tmp.add(root);
        int minDepth = 0;
        
        while(!tmp.isEmpty()){
            int count = tmp.size();
            minDepth++;
            
            for(int i = 0; i < count; i++){
               TreeNode t = tmp.poll();
               
               if(t.left == null && t.right == null){
                   return minDepth;
               }else{
                   if(t.left != null) tmp.add(t.left);
                   if(t.right != null) tmp.add(t.right);           
               }
            }
            
        }
        return minDepth; 
    }