标题形貌
输入一棵二叉搜刮树，将该二叉搜刮树转换成一个排序的双向链表。如下图所示
示例
输入：{10,6,14,4,8,12,16}
输出：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
阐明：输入题面图中二叉树，输出的时间将双向链表的头节点返回即可。
思绪方法
观察标题标特点我们可以相识到，输出是按照中序遍历输出的，那么这就成为了我们标题标突破点。
要让输出的链表是双向链表，那么就必要通过二叉树的左右子树的指向发生改变来实现。
两个重要的全局变量：
1、head：记录输出的头节点
2、pre：记录遍历当前的上一个节点，在下方代码的第一次判空中：由于当遍历到最左下的节点时，其就是为输出链表的头节点，pre也就不会再为空，那么head就固定了，也就是二叉树的左下节点，以是这两个变量都需界说为全局变量。
/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public TreeNode head = null; public TreeNode pre = null; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null){ return null; } Convert(pRootOfTree.left); if(pre==null){ pre = pRootOfTree; head = pRootOfTree; }else{ pre.right = pRootOfTree; pRootOfTree.left = pre; pre = pRootOfTree; } Convert(pRootOfTree.right); return head; } } |
