《剑指offer》– 从上往下打印二叉树、二叉搜素树的后序遍历、二叉树中和为某一值的路径、二叉树与双向链表

一、从上往下打印二叉树：

1、题目：

上往下打印出二叉树的每个节点，同层节点从左至右打印。

2、解题思路：

用arraylist模拟一个队列来存储相应的TreeNode。

3、代码实现：

public class Test9 {

	 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		 
		 ArrayList<Integer> list=new ArrayList<Integer>();
		 if(root == null){
			 return list;
		 }
		 
		 ArrayList<TreeNode> queen=new ArrayList<TreeNode>();
		 queen.add(root);
		 while(queen.size()!=0){
			 TreeNode temp=queen.remove(0);
			 
			 if(temp.left!=null){
				 queen.add(temp.left);
			 }
			 if(temp.right!=null){
				 queen.add(temp.right);
			 }
			 
			 list.add(temp.val);
		 }
		 return list;
	 }
}

class TreeNode{
	int val = 0;
    TreeNode left = null;
    TreeNode right = null;

	public TreeNode(int val) {
        this.val = val;
    }
}

二、二叉搜索树的后序遍历：

1、题目：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同

2、解题思路：

已知条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。
（1）确定root；
（2）遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；
（3）遍历右子树，若发现有小于root的值，则直接返回false；
（4）分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。

3、代码实现：

public class Test10 {

	public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
        	return false;
        }
        if(sequence.length==1){
        	return true;
        }
		
		return judge(sequence,0,sequence.length-1);
    }
	
	public boolean judge(int [] sequence,int startIndex,int rootIndex){
		
		if(startIndex>rootIndex){
			return true;
		}
		int i=startIndex;
		//找到右子树的第一个节点的下标
		while(sequence[i]<sequence[rootIndex]){
			i++;
		}
		
		for(int j=i;j<rootIndex;j++){
			if(sequence[j]<sequence[rootIndex]){
				return false;
			}
		}
		return judge(sequence,startIndex,i-1)&&judge(sequence,i,rootIndex-1);
	}
}

三、二叉树中和为某一值的路径：

1、题目

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)。

2、解题思路：

 （1）root入栈，跳入该子树进行寻路操作 ；
 （2）若root的这条路径，已满足要求，则将该路径加入到listAll中去；
 （3）对root左右子树，继续寻路；
 （4）root出栈，该子树访问完毕；

3、代码实现：

public class Test11 {

	private ArrayList<ArrayList<Integer>> resultList=new ArrayList<>();//最终返回的resultList
	private ArrayList<Integer> list= new ArrayList<>();
	
	 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

		 find(root,target);
		 
		 //对resultList的进行按长度排序
		 Collections.sort(resultList,new Comparator<ArrayList<Integer>>() {
			@Override
			public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
				return o2.size()-o1.size();
			}
		 });
		 
		 return resultList;
	 }
	 
	 public void find(TreeNode root,int target){
		 if(root==null){
			 return ;
		 }
		 list.add(root.val);
		 target=target-root.val;
		 
		 if(target==0 && root.left==null && root.right==null){
			 resultList.add(new ArrayList<Integer>(list));
		 }
		 
		 //如果提前超过target的值，则终止遍历，不继续查找子节点
		 if(target<0){
			 list.remove(list.size()-1);
			 return ;
		 }
		 
		 find(root.left,target);
		 find(root.right,target);
		 
		 //回退
		 list.remove(list.size()-1);
	 }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}

四、二叉树与双向链表：

1、题目：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

2、解题思路：

代码中有注释。

3、代码实现：

public class Test13 {
	
	//第二种递归方式：
	//改进步骤2：
	//记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点
	protected TreeNode leftLast = null;
	public TreeNode Convert2(TreeNode pRootOfTree) {
		if(pRootOfTree == null){
    		return null;
    	}
    	if(pRootOfTree.left == null && pRootOfTree.right == null){
    		leftLast = pRootOfTree;
    		return pRootOfTree;
    	}
    	
    	//1、将左子树构造成双链表，并返回链表头结点。
    	TreeNode left=Convert2(pRootOfTree.left);
    	
    	//3、如果左子树的链表不为空的话，将当前root追加到左子树链表
    	if(left!=null){
    		leftLast.right = pRootOfTree;
    		pRootOfTree.left=leftLast;
    	}
    	
    	leftLast = pRootOfTree;//当根节点只含左子树时，则该根节点为最后一个节点。
    	
    	//4、将右子树构造成双链表，并返回链表头结点
    	TreeNode right= Convert2(pRootOfTree.right);
    	
    	//5、如果右子树链表不为空的话，将该链表追加到root节点
    	if(right!=null){
    		right.left=pRootOfTree;
    		pRootOfTree.right=right;
    	}
    	return left!=null?left:pRootOfTree;
	}
	
	
	//第一种递归方式：
	public TreeNode Convert(TreeNode pRootOfTree) {
    	if(pRootOfTree == null){
    		return null;
    	}
    	if(pRootOfTree.left == null && pRootOfTree.right == null){
    		return pRootOfTree;
    	}
    	
    	//1、将左子树构造成双链表，并返回链表头结点。
    	TreeNode left=Convert(pRootOfTree.left);
    	TreeNode p=left;
    	
    	//2、定位至左子树双链表最后一个节点
    	while(p!=null && p.right!=null){
    		p=p.right;
    	}
    	
    	//3、如果左子树的链表不为空的话，将当前root追加到左子树链表
    	if(left!=null){
    		p.right = pRootOfTree;
    		pRootOfTree.left=p;
    	}
    	
    	//4、将右子树构造成双链表，并返回链表头结点
    	TreeNode right= Convert(pRootOfTree.right);
    	
    	//5、如果右子树链表不为空的话，将该链表追加到root节点
    	if(right!=null){
    		right.left=pRootOfTree;
    		pRootOfTree.right=right;
    	}
    	
    	return left!=null?left:pRootOfTree;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}