《剑指offer》– 二叉树的下一个结点、对称二叉树、按之字性顺序打印二叉树、把二叉树打印成多行

一、二叉树的下一个结点：

1、题目：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

2、解题思路：

分析二叉树的下一个节点，一共有以下情况：
（1）二叉树为空，则返回空；
（2）节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
（3）节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复第三步的判断，返回结果。

3、代码实现：

public class Test15 {
	
	 public TreeLinkNode GetNext(TreeLinkNode pNode){
		 
		 if(pNode == null){
			 return null;
		 }
		 if(pNode.right != null){
			 pNode = pNode.right;
			 while(pNode.left!=null){
				 pNode = pNode.left;
			 }
			 return pNode;
		 }
		 while(pNode.next!=null){
			 TreeLinkNode parent = pNode.next;
			 if(parent.left==pNode){
				 return parent;
			 }
			 pNode = pNode.next;
		 }
		 return null;
    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;//指向改节点的父节点
    TreeLinkNode(int val) {
        this.val = val;
    }
}

二、对称二叉树：

1、题目：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

2、解题思路：

最简单的方式可以使用递归方式，但是使用递归无法挖掘这道题的价值，因此我们可以使用DFS和BFS。

3、代码实现：

（1）第一种：递归算法：

①只要pRoot.left和pRoot.right是否对称即可。

②左右节点的值相等且对称子树left.left，right.right ;left.rigth,right.left也对称。

public class Test16 {

	boolean isSymmetrical(TreeNode pRoot){
		if(pRoot == null) return true;
		return judge(pRoot.left,pRoot.right);
    }
	
	boolean judge(TreeNode leftNode,TreeNode rightNode){
		if(leftNode == null) return rightNode==null;
		if(rightNode == null) return false;
		if(leftNode.val != rightNode.val) return false;
		return judge(leftNode.left,rightNode.right) && judge(leftNode.right,rightNode.left);
	}
	
}

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

    }
}

（2）第二种方法：DFS深度优先遍历：

DFS使用stack来保存成对的节点，

①出栈的时候也是成对成对的：

若都为空，继续；

一个为空，返回false;

不为空，比较当前值，值不等，返回false；

②确定入栈顺序，每次入栈都是成对成对的，如left.left，right.right ；left.rigth，right.left

	boolean isSymmetrical2(TreeNode pRoot){
		//第二种方法：使用深度遍历：利用Stack实现
		if(pRoot==null) return true;
		
		Stack<TreeNode> stack = new Stack<>();
		//入栈和出栈都需要成对
		stack.push(pRoot.left);
		stack.push(pRoot.right);
		while(!stack.isEmpty()){
			//成对取出
			TreeNode right = stack.pop();
			TreeNode left = stack.pop();
			if(left==null && right==null) continue;
			if(left==null ||right==null) return false;
			if(left.val!=right.val) return false;
			
			//成对入栈：
			stack.push(left.left);
			stack.push(right.right);
			stack.push(right.left);
			stack.push(left.right);
		}
		return true;
	}

（3）第三种方法：BFS广度优先遍历：

BFS使用Queue来保存成对的节点，代码和上面极其相似

①出队的时候也是成对成对的 

若都为空，继续；

一个为空，返回false;

不为空，比较当前值，值不等，返回false；

②确定入队顺序，每次入队都是成对成对的，如left.left，right.right ；left.rigth，right.left。

	boolean isSymmetrical3(TreeNode pRoot){
		//第三种方法：使用广度遍历：使用队列实现
		if(pRoot==null) return true;
		Queue<TreeNode> queue = new LinkedList<>();
		
		queue.offer(pRoot.left);
		queue.offer(pRoot.right);
		
		while(!queue.isEmpty()){
			//成对取出
			TreeNode right = queue.poll();
			TreeNode left = queue.poll();
			
			if(left ==null && right ==null) continue;
			if(left==null || right==null) return false;
			if(left.val != right.val) return false;
			
			//成对插入
			queue.offer(left.left);
			queue.offer(right.right);
			queue.offer(left.right);
			queue.offer(right.left);
		}
		return true;
	}

三、按之字性顺序打印二叉树：

1、题目：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

2、解题思路：

利用栈先进后出的性质，创建两个栈分别存放奇数层与偶数层的节点。

3、代码实现：

public class Test18 {
	public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
		int layer = 1;
		//s1存奇数层节点：
		Stack<TreeNode> s1 = new Stack<TreeNode>();
		s1.push(pRoot);
		//s2存放偶数层节点：
		Stack<TreeNode> s2 = new Stack<TreeNode>();
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		
		while(!s1.empty() || !s2.empty()){
			if(layer%2 !=0){
				//奇数层：
				ArrayList<Integer> temp = new ArrayList<Integer>();
				while(!s1.empty()){
					TreeNode node = s1.pop();
					if(node!=null){
						temp.add(node.val);
						s2.push(node.left);
						s2.push(node.right);
					}
				}
				if(!temp.isEmpty()){
					list.add(temp);
					layer++;
				}
			}else{
				//偶数层：
				ArrayList<Integer> temp = new ArrayList<Integer>();
				while(!s2.isEmpty()){
					TreeNode node = s2.pop();
					if(node!=null){
						temp.add(node.val);
						s1.push(node.right);
						s1.push(node.left);
					}
				}
				if(!temp.isEmpty()){
					list.add(temp);
					layer++;
				}
			}
		}
		return list;
    }
}

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

四、把二叉树打印成多行：

1、题目：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

2、代码实现：

public class Test19 {
	
	 ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
		 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		 if(pRoot == null){
			 return result;
		 }
		 
		 Queue<TreeNode> queue = new LinkedList<TreeNode>();
		 ArrayList<Integer> queueList = new ArrayList<Integer>();
		 queue.add(pRoot);
		 int start = 0 ,end = 1;

		 while(!queue.isEmpty()){
			 TreeNode current = queue.remove();
			 queueList.add(current.val);
			 start++;
			 if(current.left!=null){
				 queue.add(current.left);
			 }
			 if(current.right!=null){
				 queue.add(current.right);
			 }
			 if(start == end){
				 end = queue.size();
				 start=0;
				 result.add(queueList);
				 queueList = new ArrayList<Integer>();
			 }
			 
		 }
		 return result;
    }
}

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