剑指offer

103.输入一个链表，从尾到头打印链表每个节点的值。

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
        Stack<Integer>stack=new Stack<Integer>();
        ArrayList<Integer>arrayList=new ArrayList<Integer>();
         if(listNode==null)
            return arrayList;
        while(listNode!=null)
            {
            stack.add(listNode.val);
            listNode=listNode.next;
            }
        while(!stack.empty()){
            arrayList.add(stack.pop());
        }
        return arrayList;
    }
}

------------------------------------------------------------------------------------------------------------------------------------------

104.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

import java.util.ArrayList;
public class Solution {
	 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
	TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
	return root;	 
	    }
private	TreeNode reConstructBinaryTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd)
		{
	if(preStart>preEnd||inStart>inEnd)
        return null;
			TreeNode root=new TreeNode(pre[preStart]);
			for(int i=inStart;i<=inEnd;i++)
				if(in[i]==pre[preStart])
			{
				root.left=reConstructBinaryTree(pre,preStart+1,preStart+i-inStart,in,inStart,i-1);
				root.right=reConstructBinaryTree(pre,preStart+i-inStart+1,preEnd,in,i+1,inEnd);
			}
			
			return root;		
		}
}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

111.输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，

原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，

而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。

这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。

如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，

就可以进行多少次这样的操作。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
    }
}

-------------------------------------------------------------------------------------------------------------------------------------------

114输入一个链表，输出该链表中倒数第k个结点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
 if(head==null||k<=0)
			 return null;
    ListNode pre=head;
    ListNode last=head;
    for(int i=1;i<k;i++)
    {
      if(pre.next!=null)
      pre=pre.next;
      else
   	return null;
    }
   while(pre.next!=null)	
    {
	pre=pre.next;
	last=last.next;
    }
   return last;		 
    }
}

--------------------------------------------------------------------------------------------------------------------------------------------------------

115输入一个链表，反转链表后，输出链表的所有元素

public class Solution {
    public ListNode ReverseList(ListNode head) {
       if (head == null)
       return head;
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
   ListNode prev = dummy.next;
   ListNode pCur = prev.next;
   while (pCur != null) {
   prev.next = pCur.next;
   pCur.next = dummy.next;
   dummy.next = pCur;
   pCur = prev.next;
          }
  return dummy.next;
    }
}

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

116输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null)
        	return list2;
        if(list2==null)
        	return list1;
        ListNode res=null;
        if(list1.val<list2.val)
        {
        	res=list1;
        	res.next=Merge( list1.next,list2);
        }
        else
        {
        	res=list2;
        	res.next=Merge( list2.next,list1);
        }
        return res;
    }
}

117.输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null||root2==null)
        	return false;
        boolean flag=false;
        if(root1.val==root2.val)
        	flag=isSubtree(root1,root2);
        if(!flag)
        {
        	flag=HasSubtree(root1.left,root2);
        	  if(!flag)
        		  flag=HasSubtree(root1.right,root2);
        }
        	return flag;  
    }
public boolean isSubtree(TreeNode root1,TreeNode root2)
{
	if(root2==null)
		return true;
	if(root1==null&&root2!=null)
		return false;
	if(root1.val==root2.val)
	return isSubtree(root1.left,root2.left)&&isSubtree(root1.right,root2.right);
	else
		return false;
}
}

118

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:

二叉树的镜像定义：源二叉树
            8
           /  \
          6   10
         / \     / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \      / \
        11 9 7  5

import java.util.Stack;
public class Solution {
	 public void Mirror(TreeNode root) {
	       if(root==null) 
	    	   return;
		 Stack<TreeNode>stack=new Stack<TreeNode>();
		 stack.push(root);
		 while(!stack.empty())
		 {
			 TreeNode node=stack.pop();
			 if(node.left!=null||node.right!=null)
			 {
				 TreeNode nodeleft=node.left;
				 TreeNode noderight=node.right;
				 node.left=noderight;
				 node.right=nodeleft;
			 }
				if(node.left!=null) 
					stack.push(node.left);
				if(node.right!=null)
			 stack.push(node.right); 
		 }
	    }
}

-----------------------------------------------------------------------------------------------------------------

119输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       int n=matrix.length;
	   int m=matrix[0].length;
       ArrayList<Integer>res=new ArrayList<Integer>();
        int i=0;
        int j=0;
        int startX=0;
        int endX=m-1;
        int startY=0;
        int endY=n-1;
        while(startX<=endX&&startY<=endY)
        {
            if(startX==endX)
                {
                for(;i<=endY;i++)
                res.add(matrix[i][j]); 
                return res;
                }
            if(startY==endY)
                {
                for(;j<=endX;j++)
                res.add(matrix[i][j]); 
                return res;
                }
               
          for(;j<endX;j++)
              res.add(matrix[i][j]);
            
          for(;i<endY;i++)
              res.add(matrix[i][j]);
            
          for(;j>startX;j--)
              res.add(matrix[i][j]);
            
          for(;i>startY;i--)
              res.add(matrix[i][j]);
            i++;
            j++;
            startX++;
            endX--;
            startY++;
            endY--;
            
        }
  return res; 
    }
}

120.定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

import java.util.Stack;
import java.util.Iterator;
public class Solution {
	 Stack<Integer>stack=new Stack<Integer>();
    public void push(int node) {
       stack.push(node);        
    }
    public void pop() {
       stack.pop(); 
    }
    public int top() {
        return stack.peek();
    } 
    public int min() {
        int min=stack.peek();
        int tmp=0;
        Iterator<Integer>iterator=stack.iterator();
        while(iterator.hasNext())
        {
        	tmp=iterator.next();
        	min=min<=tmp?min:tmp;
        }
        return min;
    }
}

201输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，

但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack <Integer> stack=new  Stack<Integer> ();
        int j=0;
        for(int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            while(!stack.empty()&&stack.peek()==popA[j]){
                j++;
                stack.pop();
  
            }  
        }
        if(stack.empty())
            return true;
        return false;
    }
}

import java.util.LinkedList;
import java.util.Deque;
public class Solution {
	 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		 ArrayList<Integer>res=new ArrayList<Integer>();
         if(root==null)
             return res;
		 Deque<TreeNode>deq=new LinkedList<TreeNode>();
		 deq.add(root);
		 while(!deq.isEmpty())
		 {
			 TreeNode t=deq.pop();
			 res.add(t.val);
			 if(t.left!=null)
				 deq.add(t.left);
			 if(t.right!=null)
				 deq.add(t.right); 
		 }
		 return res; 
	    }
}

209.输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

topK问题，可以用堆解决。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
	ArrayList<Integer>result=new ArrayList<Integer>();
	int length = input.length;
    if(k > length || k == 0){
        return result;
    }
	PriorityQueue<Integer>maxHeap=new PriorityQueue<Integer>(k,new Comparator<Integer>(){

		@Override
		public int compare(Integer o1, Integer o2) {
			// TODO Auto-generated method stub
			return o2.compareTo(o1);
		}
	});
	for(int i=0;i<length;i++){
		if(maxHeap.size()!=k){
			maxHeap.offer(input[i]);
		}
		else
			if(maxHeap.peek()>input[i])
		{
			maxHeap.poll();
			maxHeap.offer(input[i]);
		}
	}
		for(Integer i:maxHeap){
			result.add(i);
		}	
	return result;
    }
}

----------------------------------------------------------------------------------------------------------------------------------------------------------

210.连续子数组和最大

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0)
            return 0;
         int max=array[0];
         int total=array[0];
        for(int i=1;i<array.length;i++)
            {
            if(total>0)
                total+=array[i];
            else
                total=array[i];   
            max=max>total?max:total;
            
            }
        return max;
    }
}

211求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,

但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int sum=0;
        for(int i=1;i<=n;i++)
         {
             int tmp=0;
             String str=String.valueOf(i);
             for(int j=0;j<str.length();j++)
             {
                  if(str.charAt(j)=='1')
                   tmp++;
             }
            sum+=tmp;
         }
        return sum;   
    }
 
}

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，

则打印出这三个数字能排成的最小数字为321323。

import java.util.*;
public class Solution {
	 public String PrintMinNumber(int [] numbers) {
            if(numbers.length==0)
	    return "";
            int len=numbers.length;
            compSort(numbers,len);
            String[] str=new String[len];
            for(int i=0;i<len;i++)
	     str[i]=String.valueOf(numbers [i]);
            StringBuffer sb=new StringBuffer();
             for(int i=0;i<len;i++)
	      sb.append(str[i]);
              return sb.toString();
	    }
private void compSort(int[] ch,int length)
{
	for(int i=0;i<length-1;i++)
		for(int j=i+1;j<length;j++)
		{
			int mark1=1,mark2=1,m=ch[i],n=ch[j];
			while(m>=1)
			{
				m/=10;
				mark1*=10;
			}
			while(n>=1)
			{
				n/=10;
				mark2*=10;
			}
		if(ch[i]*mark2+ch[j]>ch[j]*mark1+ch[i])
		{
			ch[i]=ch[i]+ch[j];
			ch[j]=ch[i]-ch[j];
			ch[i]=ch[i]-ch[j];
		}
		}	
}
}

----------------------------------------------------------------------------------------------------------------------------------

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。如果字符串为空,返回-1

import java.util.LinkedHashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        LinkedHashMap<Character,Integer>map=new LinkedHashMap<Character, Integer>();
	      int time=0;
	      for(int i=0;i<str.length();i++){
	    	  if(map.containsKey(str.charAt(i))){
	    		  time=map.get(str.charAt(i));
	    		  map.put(str.charAt(i), ++time);//不能用time++
	    	  }
	    	  else
	    		  map.put(str.charAt(i), 1);
	      }
		 for(int i=0;i<str.length();i++){
			 if(map.get(str.charAt(i))==1){
				 return i;
			 }
			 
		 }
		return -1;
    }
}

----------------------------------------------------------------------------------------------------------------------------------------------------------------

216输入两个链表，找出它们的第一个公共结点。

public class Solution {
    /**
     * 思路：如果有公共节点，1）若两个链表长度相等，那么遍历一遍后，在某个时刻，p1 == p2
     *                   2)若两个链表长度不相等，那么短的那个链表的指针pn（也就是p1或p2）
     *                     必先为null，那么这时再另pn = 链表头节点。经过一段时间后，
     *                     则一定会出现p1 == p2。
     *      如果没有公共节点：这种情况可以看成是公共节点为null，顾不用再考虑。
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2) {
            if(p1 != null) p1 = p1.next;    //防止空指针异常
            if(p2 != null) p2 = p2.next;
            if(p1 != p2) {                  //当两个链表长度不想等
                if(p1 == null) p1 = pHead1;
                if(p2 == null) p2 = pHead2;
            }
        }
        return p1;
    }
}

---------------------------------------------------------------------------------------------------------------------------------------------------

217统计一个数字在排序数组中出现的次数

public class Solution {
	 public int GetNumberOfK(int [] array , int k) {
	       
		 int length=array.length;
		 if(length==0)
			 return 0;
		 int firstK = getFirstK(array, k, 0, length-1);
	        int lastK = getLastK(array, k, 0, length-1);
	        if(firstK != -1 && lastK != -1){
	             return lastK - firstK + 1;
	        }
	        return 0;
	    }
	 private int getFirstK(int []array,int  k, int start, int end){
		 int mid=(start+end)>>1;
		 while(start<=end)
		 {
			 if(array[mid]<k){
					start=mid+1;
			 }
			 else
				 {
				 end=mid-1;
				 }
			mid=(start+end)/2;
		 }
		 return start;
	 }
private int getLastK(int []array,int  k, int start, int end){
	int mid=(start+end)>>1;
	 while(start<=end)
	 {
		 if(array[mid]<=k){
				start=mid+1;
		 }
		 else
			 {
			 end=mid-1;
			 }
		mid=(start+end)/2;
	 }
	 return end;	
} 
}

-----------------------------------------------------------------------------------------------------------------------------------

218输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        return TreeDepth(root.left)>TreeDepth(root.right)?(TreeDepth(root.left)+1):(TreeDepth(root.right)+1);  
    }
}

219输入一棵二叉树，判断该二叉树是否是平衡二叉树。

public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
   if(root==null) 
	   return true;
   int leftDep=TreeDepth(root.left);
   int rightDep=TreeDepth(root.right);
	if(leftDep-rightDep>1||leftDep-rightDep<-1)
		return false;
	return(IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right));
    }
public int TreeDepth(TreeNode root)
{
	if(root==null)
		return 0;
	int max=1+TreeDepth(root.left)>1+TreeDepth(root.right)?1+TreeDepth(root.left):1+TreeDepth(root.right);
	return max; 
}
}

220一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.*;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        ArrayList<Integer>al=new ArrayList<Integer>();
        for(int i=0;i<array.length;i++)
        {
            if(al.contains(array[i]))
                al.remove(new Integer(array[i]));
            else
                al.add(array[i]);
        }
        
        num1[0]=al.get(0);
        num2[0]=al.get(1);
        
    }
}

---------------------------------------------------------------------------------------------------------------------------------------------------

301小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。

但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。

现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

import java.util.ArrayList;
/*
*初始化small=1，big=2;
*small到big序列和小于sum，big++;大于sum，small++;
*当small增加到(1+sum)/2是停止
*/
public class Solution {
	public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
		ArrayList<ArrayList<Integer> >lists=new ArrayList<ArrayList<Integer> >();
		if(sum<=1)   
			return lists;
		int small=1;
		int big=2;
		while(small!=(1+sum)/2){
			int curSum=sumOfList(small,big);
			if(curSum==sum)
			{
				ArrayList<Integer>list=new ArrayList<Integer>();
				for(int i=small;i<=big;i++)
					list.add(i);
				lists.add(list);
				small++;  //不能忘记符合条件时对数据的增加
                big++;
			}
			else if(curSum<sum)
			{
                big++;
            }else
            {
                small++;
            }
        }
        return lists;
		}
	private int sumOfList(int start,int end){
		int sum=0;
		for(int i=start;i<=end;i++){
			sum+=i;
		}
		return sum;
	}
}

//根据数学公式计算:(a1+an)*n/2=s  n=an-a1+1
 
      //(an+a1)*(an-a1+1)=2*s=k*l(k>l)
 
      //an=(k+l-1)/2  a1=(k-l+1)/2
 
import java.util.ArrayList;
public class Solution {
        public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
            ArrayList<ArrayList<Integer>>list=new ArrayList<ArrayList<Integer>>();
            if(sum<3)return list;
            int s=(int) Math.sqrt(2*sum);
            for(int i=s;i>=2;i--)
                {
                    if(2*sum%i==0)
                        {
                            int d=2*sum/i;
                            if(d%2==0&&i%2!=0||d%2!=0&&i%2==0)
                                {
                                    int a1=(d-i+1)/2;
                                    int an=(d+i-1)/2;
                                    ArrayList<Integer>temp=new ArrayList<Integer>();
                                    for(int j=a1;j<=an;j++)
                                        temp.add(j);
                                    list.add(temp);
                                }
                        }
                }
            return list;
        }
}

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。

对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，

即“XYZdefabc”。是不是很简单？OK，搞定它！

public class Solution {
    public String LeftRotateString(String str,int n) {
        int len=str.length();
        if(len == 0) 
            return "";
        str+=str;
        return str.substring(n, n+len);
    }
}

---------------------------------------------------------------------------------------------------------------------------------------

一个链表中包含环，请找出该链表的环的入口结点。

第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x;

n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。

public class Solution {
 
    ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead == null || pHead.next == null)
            return null;
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        while(p2 != null && p2.next != null ){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){
                p2 = pHead;
                while(p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next;
                }
                if(p1 == p2)
                    return p1;
            }
        }
        return null;
    }
}

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

public class Solution {
	boolean isSymmetrical(TreeNode pRoot)
    {
         if(pRoot==null) 
    	   return true;
       return isSymmetrical(pRoot.left, pRoot.right);	
    }
	private boolean isSymmetrical(TreeNode left, TreeNode right)
	{
		if(left==null&&right==null)
			return true;
		if(left==null||right==null)
			return false;
		if(left.val==right.val)
			return isSymmetrical(left.left, right.right)&&isSymmetrical(left.right, right.left);
		return false;
	}
}

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
	ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>>res=new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer>tmp=new ArrayList<Integer>();
		if(pRoot==null)
			return res;
		Stack<TreeNode>list1=new Stack<TreeNode>();
		Stack<TreeNode>list2=new Stack<TreeNode>();
		list1.push(pRoot);
	while(!list1.empty()||!list2.empty())
	{
		if(!list1.empty())
		{
			while(!list1.empty())
			{
				TreeNode p=list1.pop();
				tmp.add(p.val);
				if(p.left!=null)
					list2.add(p.left);
				if(p.right!=null)
					list2.add(p.right);
			}
			res.add(new ArrayList<Integer>(tmp));
			tmp.clear();
		}
		if(!list2.empty())
		{
			while(!list2.empty())
			{
				TreeNode p=list2.pop();
				tmp.add(p.val);
				if(p.right!=null)
					list1.add(p.right);
				if(p.left!=null)
					list1.add(p.left);
			}
			res.add(new ArrayList<Integer>(tmp));
			tmp.clear();	
		}	
	}		
	return res;	
    }
}

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行

import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
	ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer> >res=new ArrayList<ArrayList<Integer> >();
		ArrayList<Integer>tmp=new ArrayList<Integer>();
		LinkedList<TreeNode> q = new LinkedList<TreeNode>();
		if(pRoot==null)
			return res;
		q.add(pRoot);
		int now=1,next=0;
		while(!q.isEmpty())
		{
			TreeNode t=q.remove();
			now--;
			tmp.add(t.val);
			if(t.left!=null)
			{
				q.add(t.left);
				next++;
			}
			if(t.right!=null)
			{
				q.add(t.right);
				next++;
			}
			if(now==0)
			{
				res.add(new ArrayList<Integer>(tmp));
				tmp.clear();
				now=next;
				next=0;
			}			
		}	
		return res;
    }
}

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

public class Solution {
	TreeNode KthNode(TreeNode pRoot, int k)
    {
		if(k<=0||pRoot==null)
			return null;
        Stack<TreeNode>LDRstack=new  Stack<TreeNode>();
        TreeNode p=pRoot;
		TreeNode res=null;
		int count=0;
		while(p!=null||!LDRstack.isEmpty())
		{
			while(p!=null)
			{
				LDRstack.push(p);
				p=p.left;
			}
			TreeNode p1=LDRstack.pop();
			count++;
			if(count==k)
				res=p1;	
			p=p1.right;
		}
		
		return res;
    }
}