32.从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。例如: 给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
[ [3], [20,9], [15,7] ]思路： 我们可以将问题简化为先层序遍历，每一层存到列表里，最后再按要求处理。写一个帮助的函数，传入参数为节点和当前节点对应的层数。 每次遍历的起始，我们判断当前遍历第几层，同时是否生成了当前层的列表，如果没有就new一个新列表来保存本层数据。 判断条件是用传入当前层数flv和list.size，也就是当前层数是否有对应的列表来判断。(根节点是第0层，不用生成列表，从第一层开始生成) 然后将当前节点的值存入对应的列表中。 递归遍历当前节点的left和right，因为当前节点的子节点已经到了下一层，所以lev+1，也就是下一层对应的列表。 遍历结束后，用for循环，从第二行开始，小于list.size，每次+2。逐层处理，将其反转，最后返回list
32.代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<List<Integer>> list = new LinkedList<>(); public void help(TreeNode root,int lev){ if(lev == list.size()){ list.add(new LinkedList<>()); } list.get(lev).add(root.val); if(root.left != null)help(root.left,lev+1); if(root.right != null)help(root.right,lev+1); } public List<List<Integer>> levelOrder(TreeNode root) { if(root == null)return list; help(root,0); for(int i = 1;i < list.size();i+=2){ Collections.reverse(list.get(i)); } return list; } }结果：
36.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例：我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
思路： 由于二叉搜索树的特性，中序遍历后的结果刚好是一个顺序列表。我们只需要考虑遍历过程中如何将前后节点连接。 此处我们用left代替指向前驱节点，right指向后继节点。 先定义两个指针，pre指向当前操作节点的前一个节点。head指向头节点。 接下来写一个递归函数，参数为节点。 递归过程为:首先判断，如果传入参数为空，直接递归结束。 如果节点不为空，但是pre为空，此时代表当前的root是最小节点，也就是头节点。我们让head指向当前root，并且pre指向当前操作节点。 如果节点不为空，pre也不为空，则代表正在遍历，此时pre指向的是当前节点的前一个节点。也就是pre.right=root。因为是双向链表，我们让root.left也指向pre，完成链接。最后pre后移，指向当前的节点。进行下面的递归。 递归结束后，将尾节点和头节点进行链接，完成双向循环链表。
pre.right = head; head.left = pre;返回头节点head
代码：
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node() {} public Node(int _val) { val = _val; } public Node(int _val,Node _left,Node _right) { val = _val; left = _left; right = _right; } }; */ class Solution { Node pre,head; public void dfs(Node root){ if (root == null)return; dfs(root.left); //判断当前的pre是不是空，是空则表示当前root是链表头节点 if(pre == null){ head = root; pre = root; }else{ //pre不是空，则表示遍历过程中，pre是当前遍历过的节点 pre.right = root; root.left = pre; pre = root; } dfs(root.right); } public Node treeToDoublyList(Node root) { if(root == null)return null; dfs(root); pre.right = head; head.left = pre; return head; } }结果：
