二叉樹

題目一：二叉樹的先序周遊，中序周遊，後序周遊 ，層周遊。

思路：分别用遞歸和非遞歸實作。

題目二：輸入一顆二叉樹的跟節點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在傳回值的list中，數組長度大的數組靠前)

思路：先從跟節點周遊到葉子節點。判斷該路徑是否等于target

題目三：二叉搜素樹的後序周遊

題目四：求二叉樹的深度

思考:遞歸 left=treeDepth(root.left)  right=treeDepth(root.right)  return left>right?left+1:right+1

題目五：平衡二叉樹

思考：條件 左右節點高度小于等于1

public static void preOrder1(Tree head){
    	if(head==null){
    		return ;
    	}
    	System.out.print(head.value+" ");
    	preOrder1(head.left);
    	preOrder1(head.right);
    }
    
    public static void inOrder1(Tree head){
    	if(head==null){
    		return ;
    	}
    	inOrder1(head.left);
    	System.out.print(head.value+" ");
    	inOrder1(head.right);
    }
    
    public static void postOrder1(Tree head){
    	if(head==null){
    		return ;
    	}
    	postOrder1(head.left);
    	postOrder1(head.right);
    	System.out.print(head.value+" ");
    }
    
    public static void preOrder2(Tree head){
    	
    	System.out.print("pre-order: ");
    	if(head!=null){
    		Stack<Tree> stack=new Stack<Tree>();
    		stack.add(head);
    		while(!stack.isEmpty()){
    			head=stack.pop();
    			System.out.print(head.value+" ");
    			if(head.right!=null){
    				stack.push(head.right);
    			}
    			if(head.left!=null){
    				stack.push(head.left);
    			}
    		}
    	}
    	System.out.println();
    }
    
    public static void inOrder2(Tree head){
    	System.out.print("in-order: ");
    	if(head!=null){
    		Stack<Tree> stack=new Stack<Tree>();
    		//stack.add(head);
    		while(!stack.isEmpty()||head!=null){
    			if(head!=null){
    				stack.push(head);
    				head=head.left;
    			}else{
    				head=stack.pop();
    				System.out.print(head.value+" ");
    				head = head.right;
    			}
    		}
    	}
    	System.out.println();
    }
    
    public static void posOrder2(Tree head){
    	System.out.print("pos-order: ");
    	if(head!=null){
    		Stack<Tree> stack1=new Stack<Tree>();
    		Stack<Tree> stack2=new Stack<Tree>();
    		stack1.add(head);
    		while(!stack1.isEmpty()){
    			head=stack1.pop();
    			stack2.push(head);
    			if(head.left!=null){
    				stack1.push(head.left);
    			}
    			if(head.right!=null){
    				stack1.push(head.right);
    			}
    		}
    		while(!stack2.isEmpty()){
    			System.out.print(stack2.pop().value+" ");
    		}
    	}
    	System.out.println();
    }
           

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
	 ArrayList<ArrayList<Integer>> pathlist=new ArrayList<ArrayList<Integer>>();
	
	 Stack<Integer> path =new Stack<Integer>();
	 findPath(root,target,pathlist,path);
	 return pathlist;
        
    }

   public  void findPath(TreeNode root,int target, ArrayList<ArrayList<Integer>> pathlist,Stack<Integer> path) {
	   if(root==null){
			 return ; 
		 }
	if(root.left==null&&root.right==null){
		if(root.val==target){
			ArrayList<Integer> list =new ArrayList<Integer>();
			for(int value:path){
				list.add(value);
			}
			list.add(root.val);
			pathlist.add(list);
		}
	}else{
		path.add(root.val);
		findPath(root.left,target-root.val,pathlist,path);
		findPath(root.right,target-root.val,pathlist,path);
		path.pop();
	}
	
}
}