三个问题都是递归问题
1 重建二叉树：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
已知二叉树的中序和先序或者中序和后序，可以还原该二叉树，本例已知先序和中序，先序的第一个元素未二叉树的根节点，找到根节点在中序中的位置，则中序序列中，很节点左边的为左子树，右边为右子树，在先序中找到对应的左右子树的先序遍历，则对左右子树的先序和中序可依次确定左右子树的根节点，递归即可，代码如下：
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; } public TreeNode reConstructBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){ if(startPre>endPre||startIn>endIn){ return null; } TreeNode root=new TreeNode(pre[startPre]); for(int i=startIn;i<=endIn;i++){ if(in[i]==pre[startPre]){ root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); root.right=reConstructBinaryTree(pre,startPre+i-startIn+1,endPre,in,i+1,endPre); } } return root; } }
2 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
思路：同样利用递归解决问题，首先将根节点的左右子树镜像，递归左右子树
public class Solution { public void Mirror(TreeNode root) { if(root!=null) { TreeNode left=root.right; TreeNode right=root.left; root.left=left; root.right=right; if(root.left!=null)//刚开始写错了是把这个if写成while了 Mirror(root.left); if(root.right!=null)//开始时这个也写成while了 Mirror(root.right); } } }
3输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
首先要了解二叉搜索树的特点，其任意一个节点的左子树小于根节点值，右子树值大于根节点值，后序遍历时，最后一个节点为根节点，去掉根节点以后，后序数组分为两部分，前一部分为左子树，其值小于根节点，后一部分为右子树，其值大于根节点，且这两段都应满足同样的条件。
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length==0) return false; if(sequence.length==1) return true; return IsPostOrder(sequence,0,sequence.length-1); } public boolean IsPostOrder(int[] sequence,int begin,int end){ if(begin>=end) return true; int t=sequence[end]; int i; for(i=begin;i<end;i++){ if(sequence[i]>=t) break; } int mid=i; while(i<end){ if(sequence[i]<t) return false;//如果后一段中出现了小于根节点值的节点，则不是合法的后序序列，否则要依次遍历剩余子序列 i++; } return IsPostOrder(sequence,begin,mid-1)&&IsPostOrder(sequence,mid,end-1);//一定要记得更新end坐标 } }
