剑指offer第一天

1. 序列化二叉树

import java.util.Queue;
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null){
            return "#,";
        }
        StringBuilder str = new StringBuilder();
        str.append(root.val+",");
        str.append(Serialize(root.left));
        str.append(Serialize(root.right));
        return str.toString();
        
  }
    TreeNode Deserialize(String str) {
       if(str == null || str.length() == 0)
           return null;
        String arr[] = str.split(",");
        Queue <String> queue = new LinkedList<String>();
        for(int i=0;i<arr.length;i++){
            queue.add(arr[i]);
           
        }
         return buildTree(queue);
    }
     TreeNode buildTree(Queue<String> q){
        if(q.size()==0)
            return null;
        String str = q.poll();
        if(str == "#"|| str.equals("#"))
            return null;
        TreeNode root = new TreeNode(Integer.valueOf(str));
        root.left = buildTree(q);
        root.right = buildTree(q);
        return root;
    }
  
}

2. 二叉查找树的第k个结点

import java.util.Stack;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(k == 0)
            return null;
        int count = 0;
        TreeNode result = null;
        Stack <TreeNode> stack = new Stack<TreeNode>();
      while(pRoot!=null || !stack.isEmpty()){ 
//向左找到当前最小结点
            while(pRoot!=null){
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
//弹出栈中最小结点
        TreeNode min = stack.pop();
          System.out.println(min.val);
           count++;
          if(count == k)
              return min;
        if(!stack.isEmpty()){
//弹出栈中间第二小结点
            count++;
            pRoot = stack.pop();
            System.out.println( pRoot.val);
            if(count == k)
                return pRoot;
         //pRoot指向第二小结点的右子树
            pRoot = pRoot.right;
        } else {
         //如果栈中无结点，pRoot指向最小结点右子树
            pRoot = min.right;
        }
      }
        return result;   
        
    }


}

3. 数据流中的中位数

import java.util.Queue;
import java.util.*;
public class Solution {
    private int count = 0;
    private PriorityQueue <Integer> minPq = new PriorityQueue<Integer>();
    private PriorityQueue <Integer> maxPq = new PriorityQueue<Integer>(15,new Comparator<Integer>(){
        @Override
        public int compare(Integer o1,Integer o2){
            return o2-o1;
        } 
    });

    public void Insert(Integer num) {
        // 当前偶数个，加入最小堆
        if(count%2 == 0){
            maxPq.offer(num);
            int firstMax = maxPq.poll();
            minPq.offer(firstMax);
        } else{
            minPq.offer(num);
            int firstMin = minPq.poll();
            maxPq.offer(firstMin);
        }
        count++;
        
    
    }

    public Double GetMedian() {
        if(count%2 == 0){
            return new Double((minPq.peek()+maxPq.peek())/2);           
        } else{
            return new Double(minPq.peek());
            
        }
        
    }


}