《剑指offer》– 树的子结构、二叉树的镜像、二叉树的深度、平衡二叉树

一、 树的子结构：

1、题目：

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

2、解题思路：

这个题比较简单，利用递归的方式就可以判断B是不是A树的子结构。

3、实现代码：

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
		//当tree1和tree2都不为空的时候，才进行比较。否则直接返回false
		if(root1 ==null || root2 == null){
			return false;
		}
		
		以这个根节点为、根节点左子树、右子树 为起点判断是否包含Tree2
		return (isSubtree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right, root2));
    }


	private boolean isSubtree(TreeNode root1, TreeNode root2) {
		//以下两个if的顺序不能调换
		//如果tree2已经遍历完了，表示都可以对应上，返回true
		if(root2==null)
			return true;
		//如果tree2已经遍历完,tree1还没遍历完，返回false
		if(root1==null)
			return false;
		
		//如果根节点对应的上，那么就分别去子节点里面匹配
		if(root1.val ==root2.val){
			return (isSubtree(root1.left,root2.left) && isSubtree(root1.right, root2.right));
		}else{
			return false;
		}
	}

二、二叉树的镜像：

1、题目：

操作给定的二叉树，将其变换为源二叉树的镜像。

2、输入描述：

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

3、解决思路：

采用递归的方式，递归交换每一个父节点的两个子节点的位置。

4、实现代码：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)
            return ;
         if(root.left==null && root.right==null)
           return;
       
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        
        Mirror(root.left);
        Mirror(root.right);
    }
}

三、二叉树的深度：

1、题目：

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

2、解决思路：

递归方式和层序遍历方式都可以解决。

3、代码实现：

public class Test3 {
	
	//第二种：非递归方式:层序遍历：
	public int TreeDepth(TreeNode root) {
		if(root == null){
			return 0;
		}
		
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		//depth代表当前节点所在的层数，count代表已经遍历的节点数，nextCount代表下一层的节点数
		//当count==nextCount的时候，代表本次节点已经遍历完毕
		int depth=0,count=0,nextCount=1;
		
		while(queue.size()!=0){
			count++;
			TreeNode top = queue.poll();
			if(top.left!=null){
				queue.add(top.left);
			}
			if(top.right!=null){
				queue.add(top.right);
			}
			
			if(count==nextCount){
				depth++;
				count=0;
				nextCount=queue.size();
			}
		}
		return depth;
    }
	
	//第一种：递归方式
	public int TreeDepth1(TreeNode root) {
		if(root == null){
			return 0;
		}
		int left= TreeDepth1(root.left);
		int right =TreeDepth1(root.right);
		
		return Math.max(left, right)+1;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

四、平衡二叉树：

1、题目：

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

2、解题思路：

递归方式或者后序遍历的方式都可以解决。

3、代码实现：

public class Test5 {
	
	private boolean isBalanced = true;
	//第三种：后续遍历时，遍历到一个节点，其左右子树已经遍历  依次自底向上判断，每个节点只需要遍历一次
	public boolean IsBalanced_Solution2(TreeNode root) {
		getDepth2(root);
		return isBalanced;
	}
	
	public int getDepth2(TreeNode root){
		if(root == null){
			return 0;
		}
		int left=getDepth2(root.left);
		int right=getDepth2(root.right);
		
		if(Math.abs(left-right)>1){
			isBalanced=false;
		}
		return Math.max(left, right)+1;
	}
	
	
	//第二种方法：三种中最好的方式
	//如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，
	//则直接停止遍历，这样至多只对每个结点访问一次。
	public boolean IsBalanced_Solution1(TreeNode root) {
		return getDepth(root) !=-1;
	}
	
	public int getDepth(TreeNode root){
		if(root == null) return 0;
		int left=getDepth(root.left);
		if(left == -1 ) return -1;
		int right=getDepth(root.right);
		if(right == -1) return -1;
		
		return Math.abs(left-right)>1?-1:1+Math.max(left, right);
	}
	
	
	//第一种方法：递归方式
	//这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。
	 public boolean IsBalanced_Solution(TreeNode root) {
		 if(root == null){
			 return true;
		 }
		 return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1
		 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
	 
	 private int maxDepth(TreeNode root){
		 if(root == null){
			 return 0;
		 }
		 return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
	 }
}


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}