1 二叉树的深度

【定义】结点的层次从根开始定义，根为第一层，树中结点的最大层次为树的深度或高度。

【思路】如果一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树呢？那该树的深度就是其左、右子树深度的较大值再加1。

public int depth(Node node){
   if(node==null)
      return 0;
   
   int nLeft=depth(node.left);
   int nRight=depth(node.right);
   
   return (nLeft>nRight) ?  (nLeft+1):(nRight+1);  
}//end depth()

2 判断二叉树是平衡二叉树

【问题】输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
【思路】在遍历树的每个结点的时候，调用函数树的深度函数depth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。

//判断二叉树是否是平衡树
public boolean isBalanced(Node root){
   if(root==null) //base case
      return true;
   
   int left=depth(root.left);
   int right=depth(root.right);
   
   int diff=left-right;
   if(diff>1 || diff<-1)
      return false;
	
	return isBalanced(root.left) && isBalanced(root.right);
}//end isBalanced()

3 二叉树中和为某一值的路径

【问题】输入一个整数和一棵二叉树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
【思路】用前序遍历的方式访问到某结点时，把该结点添加到路径中，并累加该结点的值 。

1)如果是叶结点，并且路径上结点的和等于输入的值，打印出这条路径
2）如果不是叶结点，则遍历它的子结点
3）在返回到父结点之前，在路径上删除当前结点，并在和中减去当前结点的值

public void findPath(Node root, int expectedSum,Stack stack,int currentSum){
  currentSum +=roo.value;
  stack.push(root);
  
  //如果是叶结点，并且路径上结点的和等于输入的值，打印出这条路径
  boolean isLeaf= (root.left==null) && (root.right==null) ;       //前序遍历 root
  if(isLeaf && currentSum==expectedSum){
    display(stack);
  }//end if
  
  //如果不是叶结点，则遍历它的子结点
  if(root.left!=null)   //前序遍历 left
    findPath(root.left, expectedSum,stack,currentSum);
  if(root.right!=null)  //前序遍历 right
    findPath(root.right, expectedSum,stack,currentSum);
	
   //在返回到父结点之前，在路径上删除当前结点，并在和中减去当前结点的值
   currentSum-=root.value;
   stack.pop();
}//end findPath()

4 二叉树镜像

 //二叉树镜像
 //step1: change current's left child with right child
 //step2: then recurse
 //step3: base case: current==null or current has no children
 
 public void mirrorBinaryTree(Node root){
   //base case
   if(root==null)
     return ;

   Node leftChild=root.leftChild;
   Node rightChild=root.rightChild;
   if(leftChild==null && rightChild==null )
     return;
   else{
     //do something and recurse
	 Node temp=leftChild;
	 leftChild=rightChild;
	 rightChild=temp;
	 
	 mirroBinaryTree(leftChild);
	 mirroBinaryTree(rightChild);
   }//end else
 }//end mirrorBinaryTree()